『 O(某函數(shù)())』用來描述一個算法處理給定的數(shù)據(jù)大概需要多少次運(yùn)算。

　　- 大O符號是一種算法復(fù)雜度的相對表示方式。

　　這句話中有三個重要的用詞，只要理解它們，就能知道它到底是什么意思了：

　　　　1、相對(relative)：你只能比較相同的事物。你不能把一個做算數(shù)乘法的算法和排序整數(shù)列表的算法進(jìn)行比較。

　　　　　　就好比拳擊比賽需要分重量級進(jìn)行比賽一樣，這樣的比較是沒有意義的。

　　　　2、表示(representation)：大O(用它最簡單的形式)把算法間的比較簡化為了一個單一變量。這個變量的選擇基

　　　　　　于觀察或假設(shè)。例如，處理某一個問題，有三種算法可以解決，它們的時間復(fù)雜度分別是O(n)，O(logn)，O(n2)，

　　　　　　這樣就能很快比較出這三種算法的優(yōu)劣了。而里面的變量是多少，取決于算法是什么樣的模式，它們在運(yùn)算過程中

　　　　　　做了什么樣的操作。

　　　　3、復(fù)雜度(complexity)：如果排序10,000個元素花費(fèi)了我1秒，那么排序1百萬個元素會花多少時間？

　　　　　　在這個例子里，復(fù)雜度就是相對其他東西的度量結(jié)果。

　　- 算術(shù)可以讓我們更好的理解大O：

　　　　這里我們可以聯(lián)系小學(xué)學(xué)的豎式運(yùn)算來理解：

　　　　1）當(dāng)我們進(jìn)行加法運(yùn)算時，我們需要對每一位上的數(shù)做一遍加法，所以，當(dāng)我們進(jìn)行2個4位數(shù)的加法時，就需要算4次，

　　　　　　如若進(jìn)位，就需要多算一次，100位數(shù)相加就需要做100次運(yùn)算，以此類推；減法的模式和加法類似，只是借位替代了進(jìn)位；

　　　　2）我們在做乘法運(yùn)算時，需要將每1位數(shù)字與另一個數(shù)字的每1位相乘，再做加法，所以兩個n位數(shù)想乘，就要

　　　　　　先做n²次乘法，再做大概2n次加法來得到最終結(jié)果。

　　　　- 上面的兩個例子都是用來解決兩個數(shù)字的運(yùn)算問題的，但它們的模式不一樣，經(jīng)歷的過程不一樣，所以復(fù)雜度就不一樣，

　　　　加法的模式中，位數(shù)和運(yùn)算操作是成正比的，所以它的時間復(fù)雜度可以用O(n)表示；

　　　　而乘法的模式中，它是以平方的方式進(jìn)行增長，它的時間復(fù)雜度可以用O(n²+2n)表示。

　　　　我們只關(guān)心復(fù)雜度最重要的部分：乘法運(yùn)算中，我們可以把操作次數(shù)表示為：n²?+ 2n。但當(dāng)n特別大時，第二個 2n 就無關(guān)緊要。

　　　　所以只需要用O(n²)就能表示乘法運(yùn)算的時間復(fù)雜度

?

轉(zhuǎn)載于:https://www.cnblogs.com/value-code/p/8506340.html

總結(jié)

以上是生活随笔為你收集整理的时间复杂度的理解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。