給定函數的複雜性

Question

當我分析下面的代碼段的複雜性時，我發現它是O（n/2）。但在搜索互聯網時，我發現它可能是O（n）。我想知道誰是正確的。

void function(int n) { 
    int i = 1, k = 100; 
    while (i < n) { 
     k++; 
     i += 2; 
    } 
} 

Answer 1

爲O（n/2）= O（0.5N）= O（n）的。有關詳細信息，請參閱Wikipedia。

如果˚F是O（克），則存在一些Ç和Ñ使得對於所有X>Ñ，| F（X）| < = c * | g（x）|。也就是說，從輸入n起，c * g（x）主導f（x）。

由此可見爲O（n/2）= O（n）的，因爲，

• 如果F（X）= X/2和G（X）= X，那麼我們設置c = 0.5和n = 0。
• 如果F（X）= X和G（X）= X/2，然後我們設置C = 2和n = 0的。

注意，有無窮多個值ç和ñ，你可以用它來證明這一點。 （在上面我最小化了它們，但這不是必需的。）

Answer 2

上述方法中變量k的要點是什麼？無論大O符號談論的行爲在極限（隨着n的值接近無窮大）。因此，big-O符號對於比例因子和常量都是不可知的。這就是說，對於任何常數 「c」 和縮放因子 「S」

O（F（N））等同於O（S * F（N）+ C）

在您的外殼F （N）= N，S = 1/2，且c = 0。因此...

爲O（n）= O（N/2）

Answer 3

爲O（n）是相同的O（ n/2）

大O符號的想法是瞭解算法運行速度有多快，因爲您給它一個更大的輸入。因此，例如，如果您的輸入量增加了一倍，程序可能需要兩倍的時間，否則需要花費四倍的時間。由於當你改變N的值時（即，如果你將N增加10倍，N本身和N/2都相同），n和n/2的行爲都是相同的。