1つのリンクされたリスト上での操作のBig-O

Question

あなたがサイズNの単一のリンクされたリストを持っていて、最後からすべての要素に対して操作を実行したいとします。

私は、次の擬似コードを作ってみた：

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

は今、私はこのアルゴリズムがあるビッグ-Oを判断するんです。

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

しかし、私は実際にビッグ-Oであることはよく分からない：（1）、私はそれがこのようなものだと思う操作は（）Oとすると
。私はそれがO（N^2）よりもはるかに小さいと思うが、あなたはそのO（N）を言うことはできないと思う...

Answer 1

あるあなたの式は、基本的にtriangular numbersのものです合計はN（N + 1）/ 2になる。それからO()を決定するために私はあなたを残します！

これを行うより速い方法は、元のリストとは逆の新しいリストを作成し、その上で操作を実行することです。

Answer 2

あなたのアルゴリズムはO（n^2）あなたの投稿にあなたはO（n）でそれを行うことができます。

Big-O表記はアルゴリズムの時間の複雑さに拘束されたの上位であることを覚えておくことが重要です。

Answer 3

ランタイム分析が正しいか、ランタイムがsum of the arithmetic progression従って=（N²-N）であり、1 + 2 + ... + N/2

Answer 4

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）を有することができる