Big-O операции над одним связанным списком

Question

Предположим, у вас есть один связанный список размером N, и вы хотите выполнить операцию для каждого элемента, начиная с конца.

Я придумал следующий псевдокод:

while N > 0
    Current = LinkedList 
    for 0 to N
        Current = Current.tail
    end
    Operation(Current.head)
    N := N-1
end

Теперь я должен определить, какой Big-O этот алгоритм.
Предположим, что Operation () - это O (1), я думаю, что-то вроде этого:

N + (N-1) + (N-2) + ... + (N-(N-1)) + 1

Но я не уверен, что это за Big-O. Я думаю, что он определенно меньше, чем O (N ^ 2), но я не думаю, что вы также можете сказать, что это O (N) ...

Answer 1

Ваше уравнение в основном состоит из треугольных чисел и суммируется с N (N + 1) / 2 .Я оставлю вас, чтобы определить O() из этого!

Более быстрый способ сделать это - создать новый список, обратный исходному списку, а затем выполнить операции над ним.1008 *

Answer 2

1 + 2 + 3 + ... + n = n * (n + 1) / 2 = 0,5 * n ^ 2 + O (n)

Это O (n ^ 2), а O (n ^ 2) ограничено, т. Е. Не существует более низкого порядка выполнения, который бы содержал ваше время выполнения.

Более быстрый алгоритм, работающий спереди назад, может иметь O (n) вместо O (n ^ 2)

Answer 3

Ваш алгоритм O (n ^ 2) , как вы предлагаете в своем посте. Вы можете сделать это в O (n) , хотя.

Важно помнить, что нотация Big-O является верхней границей сложности времени алгоритма.

Answer 4

Ваш анализ времени выполнения правильный, время выполнения равно 1 + 2 + ... + N, что составляет сумму арифметической прогрессии и, следовательно, = (N²-N) / 2.