1

質問: より多くのスペースが必要な場合に配列のサイズを 2 倍にする (配列を実装する) スタックのコストを表す大きな表記法は何ですか? サイズは動的に大きくなりますが、小さくはなりません。

元：

N = [size]
1 = [x]
2 = [x,x]
3 = [x,x,x,x]
4 = [x,x,x,x]
5 = [x,x,x,x,x,x,x,x]
6 = [x,x,x,x,x,x,x,x]
7 = [x,x,x,x,x,x,x,x]
8 = [x,x,x,x,x,x,x,x]
9 = [x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]
10 =[x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x]

私はそれを次のように取得しました：

T(N) = Summation from i = 0, to log_2(N) of (2^i)

これはと同等です(2^(log_2(n))) + 1

O(2^N)私はこれを と解釈しlim as n -> infinity of log_2(n) = infinityます。

つまり、本質的に...これに対するビッグオーとは何ですか:(2^(log_2(n))) + 1

4

1 に答える 1

0

コードの分析を理解するのに苦労しています。むしろ、次の分析によって、実行時間が実際に O(N) になることを確信できます。

N 個の要素を格納するには、2 番目、4 番目、8 番目、16 番目、32 番目、64 番目、.....2^x 要素の後に配列のサイズを変更します (2^x = N)。

したがって、 x = log_2 N

サイズ変更操作ごとに、配列のサイズに等しいコストが発生します。したがって、サイズ変更のオーバーヘッドの合計は次のように表すことができます。

cost = 2^0 + 2^1 + 2^2 + 2^3 ......2^x
     = (2^x-1)/(2-1)    
     = 2^x - 1 
     = 2^(log_2 N) - 1 
     = N^(log_2 2)-1 
     = N-1 
     = O(N)
于 2014-03-28T10:02:55.150 に答える