анализ алгоритма на сложность времени

Question

Я написал функцию, которая объединяет два связанных списка. (Обратите внимание, что функция основана на предварительно заданном коде на случай, если вам интересно, почему я вызываю функцию node(i)).

public SLL mergeUnsorted(SLL otherList)
{
    // find length of this list
    int length = 0 ;
    Iterator itr = this.iterator() ;
    while (itr.hasNext())
    {
        Object elem  = itr.next() ;
        length++ ;
    }

    // get each node from this list and
    // add it to front of otherList list
    int i = length -1 ;
    while (i >= 0)
    {
        // returns node from this list
        SLLNode ins = node(i) ;

        ins.succ = otherList.first ;
        otherList.first = ins ;
        i-- ;
    }
    return this ;
}

первая часть O (n) вторая часть O (n)

общая сложность O (n)

или это O (n ^ 2), потому что я перебираю список дважды?

Answer 1

Двойной обход - это просто постоянный множитель. Пока множитель не зависит от n, он все равно O (n). РЕДАКТИРОВАТЬ: Тем не менее, убедитесь, что вставка в другой список постоянное время. Если время сделать это пропорционально размеру другого списка, я думаю, вы можете увидеть, что произойдет тогда.

Answer 2

Поскольку вы дважды просмотрели список, это O (2n) .. что означает O (n). Это линейный рост.

Кроме того, в большинстве языков программирования длина коллекции уже отслеживается, поэтому вы можете просто извлечь это свойство вместо повторения дважды.

Answer 3

Простой способ убедиться в этом - запустить код с разными значениями n.Попробуйте, например, 10, 100, 1000, 10000, ... пока не получите нетривиальные времена.Когда вы умножаете n на 10, что происходит со временем?Если n * 10 => время * 10, это O (n).Если n * 10 => время * 100, это O (n ² ).Между ними это может быть O (n log n).

Answer 4

Примером алгоритма O (n ^ 2) было бы что-то вроде нахождения пересечения элементов в двух массивах. Это O (n ^ 2), потому что вы берете первый элемент из первого массива и сравниваете его с каждым элементом во втором массиве. Затем вы берете второй элемент и сравниваете его с каждым элементом второго массива. повторить.

В качестве пищи для размышлений, вы можете превратить приведенный выше пример в O (n), хэшируя все элементы в одном массиве (который является O (n)), а затем проверить каждый элемент во втором массиве (также O (n) !)