#請益 #請益 請教複雜度問題
2021年8月7日 05:26
剛開始學演算法，想向大家請教這段程式的複雜度，感恩!
for(int i = 0; i < n; i++){
if(i + 1 == n){
int k = n;
while(k >= 0){
k--;
}
}
}
國立中央大學
5
文章資訊
共 14 則留言
長庚大學
B3
舉個例子
以排序法來說
可能會有最糟情況：5 4 3 2 1
可能會有最好情況：1 2 3 4 5
也可能會有平均情況：3 1 5 2 4
在以上三種情況中
雖然 n (陣列的長度) 都是一樣的
花費的時間卻有長有短
所以才會有最糟、最好跟平均的時間複雜度一說
但是
以原 po 這個例子來說
唯一的輸入就是 n
程式跑的時間就是跟 n 呈正比
一但 n 被確定了
每一行程式碼運行的次數也就決定了
那如果你說最糟是 O(n)
請問最好是？平均是？
以上個人理解
我本人也是大一小菜雞而已
國立交通大學 資訊工程學系
B3 時間複雜度並不一定只討論最糟情況，例如 quicksort 的平均複雜度是 O(nlogn)，而最糟複雜度卻是O(n^2)（考慮到每次 pivot 都選到最小或是最大的情況，不過顯然這機率太低了，期望值算起來是 O(nlogn)）。
以這一題而言，當 i 從 0 ~ n - 2 的時候都不會做事，總共執行 n - 1 次，也就是 O(n)。
然後當 i 是 n - 1 時，會再執行 n + 1 次（k 從 n 到 0），也就是 O(n)。
因此總共無論 n 是多少，固定執行 O(n) + O(n) 次，因此 best case、worst case 和平均複雜度都是 O(n)。
國立交通大學 資訊工程學系
一種幫助你估計的方式：
```
int cnt = 0;
for(int i = 0; i < n; i++){
if(i + 1 == n){
int k = n;
while(k >= 0){
k--; cnt ++;
}
}
}
printf("%d", cnt);
```
然後你自己測試不同的 n 的時候，cnt 會是多少。