大家好，我是老三，最近裸辭了，在面試。

前兩天一個面試，隻面了十分鐘就結束了——

事情是這樣的：

面試官：你能說說HashMap的數據結構嗎？

老三：數組 鍊表 紅黑樹，阿巴阿巴……

面試官：那你說說紅黑樹的查找複雜度是多少？

老三：O(logn)。

面試官：那這個複雜度的底數是多少？

老三：時間複雜度O(logn)有底數？

面試官：沒有嗎？

尬住……

面試官：那你再說一下快速排序的時間複雜度？底數是多少？

老三露出智（尴）慧（尬）的微笑……

面試官：好了，我沒什麼要問的了，這次面試到這結束吧。

結束面試之後，老三意難平，趕緊查一下。

看一下時間複雜度的定義：

在進行算法分析時， 語句中的執行次說 T ( n ) 是關于問題規模 n 的 函 數 。 金 而 分 析 T ( n ) 随 n 的變化情況并确定 T ( n ) 的 說 量級。 算法的時間複雜度，也就是算法的時間量度， 記者： T ( n )= O(f(n))。它表示随問題規模 n 的增大， 算法執行時間的增長率和f ( n ) 的增長率相同， 稱作算法的漸近時間複雜度， 簡稱為時間複雜度。 其中 f ( n ) 是問題規模 n 的某個函數。

有點抽象對不對，直接上例子，我們來意會一下。

複制代碼

int n=10; int count=1; while (count<n){ count=count*2; //時間複雜度為O(1)的運算 System.out.println(count); }

看一下，這個運算，每次 count 乘以 2 之後， 就距離n更近了一分。 也就是說：

破案了，O(logn)确實是有底數的。

這個底數是由什麼決定的呢？

算法中log級别的時間複雜度都是由于使用了分治思想，這個底數直接由分治的複雜度決定。如果采用二分法,那麼就會以2為底，，三分法就會以3為底數，其他類似。

O(logn)底數意義不大！

那問題來了，為什麼我們平時不寫底數呢？

總不能因為這個底數太難打吧……

我們注意到，時間複雜度的定義： T ( n )= O(f(n))。它表示随問題規模 n 的增大， 算法執行時間的增長率和f ( n ) 的增長率相同， 稱作算法的漸近時間複雜度，簡稱時間複雜度。

假如說我們要比較兩個函數f(n)和g(n)的增長快慢，用什麼辦法呢？

可以使用微積分裡的極限：

老三高數忘完了哈哈，不會推導，總之最後的結果是一個常數。

也就是，假如n非常大的時候，任意底數的一個對數函數都隻是相差一個常數倍而已。

所以無論底數是什麼，log級别的漸進意義是一樣的。也就是說該算法的時間複雜度的增長與處理數據多少的增長的關系是一樣的。

總之：O（logn）已經可以表達所有底數的對數了。

---

花了一個小時，無用的知識又增加了。

簡單總結，就是O(logn)有底數，但是沒有糾結的必要。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部