Почему моя временная сложность вставки в список пропусков линейна?

Question

Я реализовал список пропуска для целых чисел. При тестировании метода вставки я вставляю натуральные числа от 1 до 1000000 в цикл for со счетчиком j. Я также использую секундомер. Приложение: в реальной программе значения удваиваются, потому что я использую часовые со значениями double.PositiveInfinity в double.NegativeInfinity. (но это не должно быть проблемой) Псевдокод:

MyList = new SkipList();
stopwatch.start();    
t1 = stopwatch.Elapsed.TotalMilliseconds;
for(int j = 0; j<1000000; j++){
    steps = MyList.insert(j);
    if(j%500==0){
        t2= stopwatch.Elapsed.TotalMilliseconds -t1;
        write j,t2 in a file1;
        write j,steps in a file2;
        t1 = t2;
    }
}

Когда я делаю график время / количество узлов, он линейный, но шаги / узлы графика, как и ожидалось, логарифмические. (steps - количество циклов цикла (~ операций) в методе insert).

Метод insert создает дополнительные узлы и устанавливает несколько пуазеров. Узлы реализованы следующим образом:

class Node 
{
    public Node right;//his right neighbour - maybe "null"
    public Node down;//his bottom neighbour -maybe null
    public int? value;//value
    public int depth;//level where node is present: 0, 1, 2 ...

    public Node(int i,Node rightt,Node downn,int depthh) {
        //constructor for node with two neighbours.
        value = i;
        right = rightt;
        down = downn;
        depth = depthh;
    }
   //there are some other contructors (for null Node etc.)
}
class SkipList
{
    public Node end;//upper right node
    public Node start;//upper left node
    public int depth;//depth of SkipList
    //there are left (-inf) and right sentinels (inf) in the SkipList.
}

Пропустить список состоит из узлов.

Вставка определена в классе SkipList и работает следующим образом:

public int Insert(int value2, int depth2)
    {
        //returns number of steps
        //depth2 is calculated like (int)(-Math.Log(0<=random double<1 ,2))
        //and works as expected - probability P(depth = k) = Math.Pow(0.5,k)

        //lsit of nodes, which will get a new right neighbour
        List<Node> list = new List<Node>();
        Node nod = start;
        int steps = 0;
        while (true) {
            if (nod.right.value >= value2)
            {
                //must be added to our list
                lsit.Add(nod);
                if (nod.down != null)
                    nod = nod.down;
                else
                    break;
            }
            else {
                nod = nod.right;
            }
            steps++;
        }

        //depth (of skipList) is maybe < depth2, so we must create
        //k = 2*(depth2-depth) new edge nodes and fix right pointers of left sentinels
        List<Node> newnodes = new List<Node>();
        for (int jj = 0; jj < depth2 - depth;jj++ )
        {
            steps++;
            //new sentinels
            Node end2 = new Node(double.PositiveInfinity, end,depth+jj+1);
            Node start2 = new Vozlisce(double.NegativeInfinity, end2,
                                                               start,depth+jj+1);
            start = start2;
            end = end2;
            newnodes.Add(start2);
        }

        //fix right pointers of nodes in the List list (from the beginning)
        Node x = new Node(value,list[list.Count-1].right,0);
        list[list.Count-1].right=x;
        int j =1;
        while(j<=Math.Min(depth2,depth)){
            steps++;
            //create new nodes with value value
            x = new Node(value,lsit[list.Count -(j+1)].right,x,j);
            list[list.Count-(j+1)].right = x;
            j++;
        }
        //if there are some new edge sentinels, we must fix their right neighbours
        // add the last depth2-depth nodes
        for(int tj=0;tj<depth2-depth;tj++){
            steps++;
            x = new Node(value,newnodes[tj].right,x,depth+tj+1);
            newnodes[tj].right = x;
        }

         depth = Math.Max(depth, depth2);           
         return steps;
    }

Я также реализовал версию списка пропусков, где узлы являются блоками и имеют n = node.depth правых соседей, хранящихся в массиве, но график time/num. узлов все еще линейный (а число шагов / число узлов логарифмическое).

Answer 1

^ это "xor";

10 : 1010
 6 : 0110
---------
 ^ : 1100 = 12

Если вы выполните цикл от 0 до 11, тогда да - он будет казаться довольно линейным - вы не заметите какого-либо ухудшения по сравнению с этим размером. Вы, вероятно, хотите Math.Pow скорее, чем ^, но было бы проще жестко кодировать 1000000,