什麼是大 O 時間複雜度？

該部落格上撰寫的文章是出於教學目的而創建的。 另外，文章中的資訊可能不正確，請謹慎。

大 O 表示法表示計算量隨著輸入大小的增加而增加的速率。 其目的與準確告知需要多少奈秒的基準不同。

常見的複雜性

O(1) 數組索引訪問
O(log N) 二分查找
O(N) 完全遍歷
O(N log N) 一般比較排序
O(N²) 比較所有對

常數省略

for (int Value : Values)
{
    ProcessA(Value);
}

for (int Value : Values)
{
    ProcessB(Value);
}

由於遍歷了兩次，所以實際操作是2N靠近，但在 Big OO(N)將其表達為 這是因為它關注的是隨著 N 的增長而遞增的順序。

忽略常數並不意味著它們在實際性能中不重要。 快取友好O(N)如果您的程式碼與複雜常數不同O(N)它可以比代碼快得多。

最差、平均、最好

線性搜尋找到第一個元素O(1)，但如果它丟失或位於末尾O(N)是。 如果你不寫下你在談論哪一種情況，同樣的演算法將會有不同的解釋。

Big O 是選擇演算法的第一個過濾器。 最終選擇應根據實際資料大小、記憶體使用情況、快取和實現複雜性進行權衡。