確定複雜性等級

這裏的大標記是什麼？一個解釋將不勝感激。謝謝。確定複雜性等級

public static int[] mystery1(int[] list) { 

    int[] result = new int[2 * list.length]; 
    for (int i = 0; i < list.length; i++) { 
    result[2 * i] = list[i]/2 + list[i] % 2; 
    result[2 * i + 1] = list[i]/2; 
    } 

    return result; 

}

來源

2013-02-08 cluv

是功課嗎？ – 2013-02-08 20:43:01

本地化太大.. – Puppy 2013-02-08 20:44:17

它是O(n)，其中n是列表的長度。無論如何你都要經歷整個列表。

算術運算的數量：

2N次乘法
2N增加
2N divitions
ň模運算

這還不算算術運算實現for循環。

來源

2013-02-08 20:37:50 user000001

爲O（n）

命令的量不是作爲控制結構（循環）使用如此重要。如果你考慮這個函數，它只有一個循環。該循環使用列表（n）的長度作爲迭代次數。如果列表長度加倍，循環完成所需的時間也會增加。

來源

2013-02-08 20:39:04 Grambot

嗯，它不僅是循環。你還必須考慮你正在使用的非原始操作（尤其是遞歸調用）（尤其是遞歸對於估計複雜度有時會有點痛苦）。 – Cubic 2013-02-08 20:41:16

好的一點，任何允許程序流程去除A-> B的任何地方都有可能增加函數/算法操作的複雜度。 – Grambot 2013-02-08 21:46:29

大O表示最壞的情況。由於無法比較兩臺不同計算機執行操作所需的時間，因此Big O適用於算法執行的操作次數。操作可以是從方法調用到變量賦值的任何操作。

經歷代碼

int[] result = new int[2 * list.length]; 
    for (int i = 0; i < list.length; i++) { 
    result[2 * i] = list[i]/2 + list[i] % 2; 
    result[2 * i + 1] = list[i]/2; 
    } 

    return result;

重負載處於for循環。因爲你循環list.length次，你這個方法的大O是O(list.length)。但是，爲了徹底，您還可以進行其他操作。當你分配一個新的int數組時，你可以計算它。當您計算result數組中的索引2 * i時，您也可以這樣計算。但是，由於這些操作需要一段時間，所以它們會在循環所需的可變時間內被吞併。

你應該閱讀筆記，但你會學到，也有不同程度的複雜性，恆定的，線性的，對數的，等等

來源

2013-02-08 20:40:16

「大O代表最壞的情況。」不是真的。這是運行時漸近行爲與輸入長度的近似值。形式上大O意味着一個上限，儘管在通俗用法中它通常意味着「上限和下限」。 – Cubic 2013-02-08 20:43:36

對我來說，一個上限是最差的（時間，比方說）。 – 2013-02-08 20:45:21

@Cubic是不是下限的小o？ – user000001 2013-02-08 20:46:10

這是O（n）。因爲循環迭代只有一個。這取決於陣列的長度並將線性增長。

來源

2013-02-08 21:02:08

確定複雜性等級

回答

相關問題