最好和最壞的情況 - 時間compexity

我必須找到一個算法的最好和最壞的情況下，但我不明白的結果：最好和最壞的情況 - 時間compexity

int chOne=1; 
for (int i=0; i<list.lenght; i++) 
    if(list[i]<list[chOne]){ 
     chOne=i; 
    } 
return chOne;

BC：2C + 2C（N-1）= 2cn
WC：2c + 3c（n-1）= 3cn-c

我不知道什麼是「n-1」;並按照其他類似活動，這將是（我認爲）

BC：5C
WC：3C + 2 CN

有人能告訴我爲什麼是不是這樣？謝謝！

來源

2015-02-17 Sive

問題在哪裏？ – genisage 2015-02-17 23:33:29

爲什麼最好的情況是2cn而不是5c？ – Sive 2015-02-17 23:34:37

沒有關於問題的更多信息，我無法分辨。 'for'和'if'內的東西可能是重要的。 – genisage 2015-02-17 23:37:32

精確的數字取決於您在算法模型中考慮的原子操作。

然而，它始終認爲

整個列表被訪問，以遞增目前指數i，用於測試循環終止，並檢查在每個迭代一個新的最小值。
無論何時該列表的當前訪問元素小於由chOne索引的當前最小候選者，都會發生更新操作。

所以你最好的情況是，當沒有更新過發生（這樣的話如果chOne指數最小的列表元素的初始選擇），在最壞的情況下，更新發生在每次迭代，但1，後者是噹噹前列表索引等於原始選擇chOne（或者已經有更新，則當前索引元素不能小於當前選擇，或者原始索引chocie已經爲0）時的迭代，則兩個索引都是一樣）。

隨着n代表名單長度，2c作爲每個迭代的固定成本和c一個chOne更新的成本，你有1次迭代保證每個成本2c和n-1迭代成本至少2c和可能3c。

來源

2015-02-18 06:55:34 collapsar

最好和最壞的情況 - 時間compexity

回答

相關問題