誰能告訴我下面函式的復雜性是什么？以及如何計算復雜度？
我懷疑它是 O(log(n)) 或 O(sqrt(N))。我的推理基于 n=4、n=8、n=16 的例子，我發現回圈將采用 log(n) 但我認為這還不夠，因為 sqrt 也會給出相同的值所以我需要處理更大的 n 值，所以我不知道如何解決這個問題。
我今天考試有這個功能。
void f(int n){
int i=1;
int j=1;
while(j <= n){
i = 1;
j = i;
}
}
uj5u.com熱心網友回復：
序列j經過是1 3 6 10 15 21，又名三角形數，又名n*(n 1)/2。
展開，這是( n^2 n ) / 2。我們可以忽略縮放 ( / 2) 和線性 ( n) 因子，這給我們留下了n^2。
j增長為n^2多項式，因此回圈將在增長的倒數后停止：
時間復雜度為O(sqrt(n))
uj5u.com熱心網友回復：
這取決于你的條件。換句話說，時間復雜度是 O(log n)。相對于輸入大小 n，執行了多少陳述句？通常，但并非總是如此，我們可以從回圈迭代的次數中得到一個想法。回圈體執行 i= 2^0 2^1 2^2 .... 2^n; 這個序列有 O(log n) 個值。
有關更多詳細資訊，請查看“演算法簡介”一書。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344354.html