1

问题：如果需要更多空间，堆栈（实现数组）的成本加倍其数组大小的大哦符号是什么。它会动态调整大小，但不会更小。

前任：

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 回答