1.究竟什么是時間復雜度

時間復雜度是一個函數，它定性描述該算法的運行時間。假設算法的問題規模為n，那么操作單元數量便用函數f(n)來表示，隨著數據規模n的增大，算法執行時間的增長率和f(n)的增長率相同，這稱作為算法的漸近時間復雜度，簡稱時間復雜度，記為 O(f(n))

2.什么是大O

算法導論給出的解釋：大O用來表示上界的，當用它作為算法的最壞情況運行時間的上界，就是對任意數據輸入的運行時間的上界。

3.不同數據規模的差異

所以我們說的時間復雜度都是省略常數項系數的，是因為一般情況下都是默認數據規模足夠的大，基于這樣的事實，給出的算法時間復雜的的一個排行如下所示：

O(1)常數階 < O(logn)對數階 < O(n)線性階 < O(nlogn)線性對數階 < O(n^2)平方階 < O(n^3)立方階 < O(2^n)指數階

但是也要注意大常數，如果這個常數非常大，例如10^7 ，10^9 ，那么常數就是不得不考慮的因素了。

4.復雜表達式的化簡

有時候我們去計算時間復雜度的時候發現不是一個簡單的O(n) 或者O(n^2)， 而是一個復雜的表達式，例如：

O(2*n^2 + 10*n + 1000)

那這里如何描述這個算法的時間復雜度呢，一種方法就是簡化法。

去掉運行時間中的加法常數項 （因為常數項并不會因為n的增大而增加計算機的操作次數）。

O(2*n^2 + 10*n)

去掉常數系數（上文中已經詳細講過為什么可以去掉常數項的原因）。

O(n^2 + n)

只保留保留最高項，去掉數量級小一級的n （因為n^2 的數據規模遠大于n），最終簡化為：

O(n^2)

如果這一步理解有困難，那也可以做提取n的操作，變成O(n(n+1)) ，省略加法常數項后也就別變成了：

O(n^2)

所以最后我們說：這個算法的算法時間復雜度是O(n^2) 。

也可以用另一種簡化的思路，其實當n大于40的時候， 這個復雜度會恒小于O(3 × n^2)， O(2 × n^2 + 10 × n + 1000) < O(3 × n^2)，所以說最后省略掉常數項系數最終時間復雜度也是O(n^2)

通俗的講就是忽略量級低的，因為數據量足夠大的時候量級底的相當于沒有---高數里是這樣。

5.O(logn)中的log是以什么為底？