時空複雜度(時間複雜度/空間複雜度)O(1)、O(n)、O(n^2)、O(log n)、O(n log n)是什麼意思?

2021-02-13 架構師社區

大O符號是算法複雜度的相對表示。它描述了時空複雜度.

大O符號是我在大學裡學過的東西之一,我了解過這個算法的概念。我知道的不算多,可以回答一些基本的問題,僅此而已。從大學畢業以後,我對這個算法的了解基本沒有改變,因為自從我開始工作以來,我沒有使用過它,也沒有聽到任何同事提到過它。所,我想我應該花點時間回顧一下它,並在這篇文章中總結大O符號的基礎知識,以及一些代碼示例來幫助解釋它。

什麼是大O符號?簡而言之

它是算法複雜度的相對表示。

它描述了一個算法如何執行和縮放。

它描述了函數增長率的上限,可以考慮最壞的情況。

現在快速看一下語法:O(n2)。

n是函數作為輸入接收的元素個數。這個例子是說,對於n個輸入,它的複雜度等於 n2。

共同複雜性的比較

從這個表中可以看出,隨著函數複雜度的增加,完成一個函數所需的計算量或時間可能會顯著增加。因此,我們希望將這種增長保持在儘可能低的水平,因為如果函數不能很好地伸縮而增加了輸入,可能會出現性能問題。

顯示操作數量如何隨複雜性增加的圖表。

一些代碼示例應該有助于澄清一些關於複雜性如何影響性能的問題。下面的代碼是用Java編寫的,但是很明顯,它可以用其他語言編寫。

O(1)

public boolean isFirstNumberEqualToOne(List<Integer> numbers) {

return numbers.get(0) == 1;

}

O(1) 表示一個函數,無論輸入大小如何,該函數總是取相同的值。

O(n)

public boolean containsNumber(List<Integer> numbers, int comparisonNumber) {

for(Integer number : numbers) {

if(number == comparisonNumber) {

return true;

}

}

return false;

}

O(n)表示一個函數的複雜度,該函數的複雜度與輸入的個數成線性正比增長。這是一個很好的例子,說明大O符號如何描述最壞的情況,因為函數在讀取第一個元素後返回true,或者在讀取所有n個元素後返回false。

O(n2)

public static boolean containsDuplicates(List<String> input) {

for (int outer = 0; outer < input.size(); outer++) {

for (int inner = 0; inner < input.size(); inner++) {

if (outer != inner && input.get(outer).equals(input.get(inner))) {

return true;

}

}

}

return false;

}

O(n2)  表示一個函數,其複雜度與輸入大小的平方成正比。通過輸入添加更多的嵌套迭代將增加複雜性,然後可以用3次總迭代表示O(n3),用4次總迭代表示O(n4) 。

public int fibonacci(int number) {

if (number <= 1) {

return number;

} else {

return fibonacci(number - 1) + fibonacci(number - 2);

}

}

O(2n) 表示一個函數,其性能對輸入中的每個元素都加倍。這個例子是斐波那契數列的遞歸計算。函數屬於O(2n),因為函數對每個輸入數遞歸地調用自身兩次,直到該數小於或等於1。

O(log n)

public boolean containsNumber(List<Integer> numbers, int comparisonNumber) {

int low = 0;

int high = numbers.size() - 1;

while (low <= high) {

int middle = low + (high - low) / 2;

if (comparisonNumber < numbers.get(middle)) {

high = middle - 1;

} else if (comparisonNumber > numbers.get(middle)) {

low = middle + 1;

} else {

return true;

}

}

return false;

}

O(log n)表示一個函數,該函數的複雜度隨輸入大小的增加呈對數增長。這使得O(log n)函數可以很好地伸縮,這樣處理較大的輸入就不太可能導致性能問題。上面的示例使用二分查找來檢查輸入列表是否包含某個數字。簡單地說,它在每次迭代中將列表一分為二,直到找到數字或讀取最後一個元素。此方法具有與O(n)示例相同的功能,儘管實現完全不同且更難於理解。但是,這樣做的回報是更大的輸入會帶來更好的性能(如表中所示)。

這種實現的缺點是二進位搜索依賴於元素已經處於正確的順序。如果在遍曆元素之前需要對元素進行排序,那麼這就增加了一些開銷。

關於大O符號還有很多內容要講,但希望你們現在對大O符號的含義有了一個基本的概念以及如何將它轉換成你寫的代碼。如果有必要,大O符號還有後續要講,若有不懂,歡迎下方留言關注,我會一一解答。

長按二維碼 ▲

訂閱「架構師小秘圈」公眾號

如有啟發,幫我點個在看,謝謝↓

相關焦點

  • 時間複雜度 O(log n) 意味著什麼?
    預先知道算法的複雜度是一回事,了解其後的原理是另一件事情。不管你是計算機科班出身還是想有效解決最優化問題,如果想要用自己的知識解決實際問題,你都必須理解時間複雜度。先從簡單直觀的 O(1) 和 O(n) 複雜度說起。
  • 報導 | 複雜度O(n log n)?整數乘法新算法!
    如今,David Harvey和Joris van der Hoeven宣稱他們發現了複雜度更低的整數乘法算法。在計算機進行乘法計算的時候,傳統的計算方法採用了類似豎式計算的方法——正如我們在小學課堂裡面所學到的那樣,因此時間複雜度是O(n ^ 2)。
  • 複雜度 O、Θ、Ω、o、ω,別再傻傻分不清了!
    但是,在其他書籍中,你可能還見過Θ、Ω、o、ω等符號。那麼,這些符號又是什麼意思呢?本節,我們就來解決這個問題。比如說,f(n) = 2n^2+3n+1 = Θ(n^2),此時,g(n)就是用f(n)去掉低階項和常數項得來的,因為肯定存在某個正數n0、c1、c2,使得 0 <= c1*n^2 <= 2n^2+3n+1 <= c2*n^2,當然,你說g(n)是2*n^2也沒問題,所以,g(n)實際上滿足這個條件的一組函數。
  • 算法的時間複雜度
    算法的時間與空間複雜度事後分析法缺點:不同的數據規模,不同的機器下算法運行的時間不同,無法做到計算運行時間事前分析法大O時間複雜度漸進時間複雜度 隨著n的增長= 0; i < n ; i++){ print(n); }}這段代碼的時間複雜度為n^3+n^2+n當n足夠大時,n^2和n與n^3相比太小,可以忽略不計常見複雜度o(1)i = i + 1;o(n)test(n){
  • 一場排序引發的風波——計數排序(O(n)複雜度)
    它的優勢在於在對一定範圍內的整數排序時,它的複雜度為Ο(n+k)(其中k是整數的範圍),快於任何比較排序算法。當然這是一種犧牲空間換取時間的做法,而且當O(k)>O(n*log(n))的時候其效率反而不如基於比較的排序(基於比較的排序的時間複雜度在理論上的下限是O(n*log(n)), 如歸併排序,堆排序)對於額外數組該如何理解呢?
  • 時間複雜度中的log(n)底數是多少?
    其實這裡的底數對於研究程序運行效率不重要,寫代碼時要考慮的是數據規模n對程序運行效率的影響,常數部分則忽略,同樣的,如果不同時間複雜度的倍數關係為常數,那也可以近似認為兩者為同一量級的時間複雜度。現在來看看為什麼底數具體為多少不重要?
  • O(n)的算法居然超時了,此時的n究竟是多大?
    如果寫出了一個O(n)的算法 ,其實可以估算出來n是多大的時候算法的執行時間就會超過1s了。如果n的規模已經足夠讓O(n)的算法運行時間超過了1s,就應該考慮log(n)的解法了。也就是 2.7 GHz 奔騰雙核,i5處理器,GHz是指什麼呢,1Hz = 1/s,1Hz 是CPU的一次脈衝(可以理解為一次改變狀態,也叫時鐘周期),稱之為為赫茲,那麼1GHz等於多少赫茲呢所以 1GHz = 10億Hz,表示CPU可以一秒脈衝10億次(有10億個時鐘周期),這裡不要簡單理解一個時鐘周期就是一次
  • 為什麼排序的複雜度為 O(N log N) | Linux 中國
    這樣,共有  4×3×2×1=4!=24 種排列可供選擇。通過一次比較大小,只能產生兩種可能的結果。如果列出所有的排列,那麼「從小到大」排序對應的可能是第 8 種排列,按「從大到小」排序對應的可能是第 24 種排列,但無法知道什麼時候需要的是其它 22 種排列。通過 2 次比較,可以得到 2×2=4 種可能的結果,這仍然不夠。
  • 算法的時間複雜度和空間複雜度-總結
    (2)時間複雜度 在剛才提到的時間頻度中,n稱為問題的規模,當n不斷變化時,時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此,我們引入時間複雜度概念。按數量級遞增排列,常見的時間複雜度有:常數階O(1),對數階O(log2n),線性階O(n),線性對數階O(nlog2n),平方階O(n2),立方階O(n3),..., k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大,上述時間複雜度不斷增大,算法的執行效率越低。
  • 時間複雜度的表示、分析、計算方法……一文帶你看懂時間複雜度!
    作者 | OverRedMaple責編 | Carol來源 | CSDN 博客封圖 | CSDN付費下載於東方 IC如果你還在發愁究竟怎麼計算時間複雜度和空間複雜度根據上面兩個例子得出結論:代碼的執行時間 T(n)與每行代碼的執行次數 n 成正比,人們把這個規律總結成這麼一個公式:T(n) = O(f(n))所以呢,第一個例子中的 T(n)=O(2n+1),第二個例子中的 T(n)=O(2n*n+n+1),這就是時間複雜度表示法,
  • 從經典算法題看時間複雜度
    舉個例子,假設我們解決一個規模為 n 的問題要花費的時間為 T(n)T(n):T(n)=4n22n+2T(n)=4n22n+2當 n 不斷增大時,n2n2 開始佔據主導地位,而其他各項可以被忽略,寫作 T(n)=O(n2)T(n)=O(n2)。因此時間複雜度可被稱為是 漸近 的。
  • 時間複雜度的分析及排序算法總結
    不管n如何增⻓,都不會影響到這個函數的計算時間,因此這個代碼的時間複雜度都是O(1)。例如希爾排序,是三個for循環,但是它的時間複雜度是O(nlogn)。關於logn思考logn指的是n的對數,在數學中,n的對數必須有底數,也就是像log2n,log3n...。
  • Python-排序-快速排序,如何在O(n)內找到第K大元素?
    比如現在要時間複雜度為 O(n),在一個長度為 n 的數組中查找到第 K 大的元素,你會怎麼做呢?你可能會說這很簡單啊,第一次遍歷數組找到第 1 大元素,第二次遍歷找到第 2 大,…,第 K 次就可以找到第 K 大 但是這樣的時間複雜度就不是 O(n),而是 K*O(n),當 K 接近 n 時,時間複雜度就是 O(n^2)。
  • 算法的時間複雜度到底如何計算
    我們知道常數項對函數的增長速度影響並不大,所以當 T(n) = c,c 為一個常數的時候,我們說這個算法的時間複雜度為 O(1);如果 T(n) 不等於一個常數項時,直接將常數項省略。比如第一個 Hello, World 的例子中 T(n) = 2,所以我們說那個函數(算法)的時間複雜度為 O(1)。T(n) = n + 29,此時時間複雜度為 O(n)。
  • 關於時間複雜度,你不知道的都在這裡!
    什麼是大O這裡的大O是指什麼呢,說到時間複雜度,「大家都知道O(n),O(n^2),卻說不清什麼是大O」。算法導論給出的解釋:「大O用來表示上界的」,當用它作為算法的最壞情況運行時間的上界,就是對任意數據輸入的運行時間的上界。
  • 大O符號和代碼效率:花最少的精力得到最大的產出
    時間複雜度vs空間複雜度大O符號用於度量時間複雜度和空間複雜度。· 時間複雜度:為完成整體操作而必須執行的小操作的數量。下列是幾種較常見類型:· 常數階/O(1):無論數據集多大,始終在相同的時間或空間中執行。· 對數階/O(log n):為獲得給定數據,固定數據所必須增加的冪。· 線性階/ O(n):複雜度與輸入數據的大小直接相關。
  • 用機器學習構建O(N)複雜度的排序算法,可在GPU和TPU上加速計算
    雖然當前已有大量的卓越算法,但基於比較的排序算法對(N log N) 比較有著根本的需求,也就是 O(N log N) 時間複雜度。近年來,隨著大數據的興起(甚至萬億字節的數據),效率對數據處理而言愈為重要,研究者們也做了許多努力來提高排序算法的效率。大部分頂尖的排序算法採用並行計算來處理大數據集,也取得了卓越的成果。
  • 英文字母的象形密碼(三)l、m、n、o、p、q、r、s、t
    本文所論述,為26個英文字母中l、m、n、o、p、q、r、s、t 的來由。三、nn,其發音為「恩「。n,其象形奶頭。(無圖,腦補)n,其實際應用中切音「那(ne)」。那之本意,指柔軟彎曲的樹枝。四、oo,其發音為「藕」,象形藕孔。
  • leetcode1553_go_吃掉N個橘子的最少天數
    請你返回吃掉所有 n 個橘子的最少天數。示例 1:輸入:n = 10 輸出:4解釋:你總共有 10 個橘子。第 1 天:吃 1 個橘子,剩餘橘子數 10 - 1 = 9。第 2 天:吃 6 個橘子,剩餘橘子數 9 - 2*(9/3) = 9 - 6 = 3。