兩個非嵌套循環的大哦表示法

Question

這是我的問題，我設法給出了a部分的答案，但是對於b部分，我對b部分的答案並沒有真正的信心。

在最近的法庭案件中，法官引用了一個城市的蔑視，並在第一天訂購了2美元的罰款。每個接下來的日子，直到這個城市遵循法官的命令，這個金額被平方爲 （即，金額進展如下：2美元，4美元，16美元，256美元，65536美元......）。 a。第N天會是什麼？ b。需要多少天的時間才能達到D美元（一個大哦答案可以）？

答一：2 ^（2^N-1）

對於答案B，我做了下面的程序，找到大哦。

for (int i = 0; i < n - 1; i++) { 
    result = 2 * result; 
} 
printf("%d\t", result); 

for (int j = 0; j < result; j++) { 
    res = 2 * res ; 
} 
printf("%d\n", res); 

我算過了第一循環的大哦爲n 的Sumation公司並且由於第二循環運行2^N-1次的第一環，它的大哦，是2^n和增加他們兩個它們成爲（2^N）+ N

Answer 1

根據我的算法我的回答是O（N）

int days=5; 
int fine = 2; 
for(int i=0; i<days-1; i++) 
    fine = fine * fine; 

cout << fine; 

Answer 2

第一循環運行n-1倍，第二運行2^(n-1)次。時間複雜度 是這些的總和，所以(n-1) + 2^(n-1) = O(2^n + n) = O(2^n)。

雖然這個問題似乎沒有要求時間複雜性。這是要求 罰款達到D美元之前會通過多少天。這是 的答案a）的答案：O(log log D)（例如在log(log(65536)) + 1天后達到65536美元）。

Answer 3

你並不需要任何軟件來回答這些問題。大O是恰好用於軟件開發的數學術語。

讓我們看看進展：

2  = 2^1 = 2^(2^0) 
4  = 2^2 = 2^(2^1) 
16 = 2^4 = 2^(2^2) 
256 = 2^8 = 2^(2^3) 
65536 = 2^16 = 2^(2^4) 

回答質疑一個。

第n日的處罰爲2^(2^(n-1))。

你可以喜歡這個節目吧：

pow(2, pow(2, n-1)); 

答到問題B。

x = log2 (log2 D) + 1 

或者如果我們不計算第一天就沒有「+ 1」。
這將返回一個正實數，因此您可能需要根據要求將其設爲最小值。

現在，在大O表示法中，它將是O（log（log）），它描述了值如何增長。這意味着當輸入（D在這種情況下）乘以n時，函數的值將增加至多log(log n)次。