单个链表上的操作的大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()那个!

更快的方法是构造一个与原始列表相反的新列表,然后对其执行操作.