有關此特定成本函數的大哦表示法

問題：如果堆棧（實現數組）的成本（如果需要更多空間的話）會使數組大小增加一倍，那麼這個堆棧的成本是多少？它會動態調整大小，但不會更小。有關此特定成本函數的大哦表示法

例如：

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

來源

2014-03-28 Jake M.

**不知道**但你可以試着問這個問題在網站[計算機科學]（http://cs.stackexchange.com/） – Astrobleme

@ user3471847請考慮通過點擊下面的答案點擊複選標記來接受答案。另見http://meta.stackexchange.com/questions/135493/informing-new-users-of-how-to-accept-answers –

我有一個很難搞清楚你的代碼的分析。相反，您可以通過以下分析確信運行時間確實爲O（N）：

對於存儲N個元素，您將在第2,4,8,16,32,64， ..... 2^x的元素，其中，2^X = N.

因此，X = log_2ñ

在每個調整操作等於陣列的大小的成本費用。因此，總開銷調整大小可以表示爲：

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-28 10:02:55

有關此特定成本函數的大哦表示法

回答

相關問題