大家好，我是老三，最近裸辭了，在面試，
前兩天一個面試，只面了十分鐘就結束了——
事情是這樣的：
面試官：你能說說HashMap的資料結構嗎？
老三：陣列+鏈表+紅黑樹，阿巴阿巴……
面試官：那你說說紅黑樹的查找復雜度是多少？
老三：O(logn)，
面試官：那這個復雜度的底數是多少？
老三：時間復雜度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)有底數，但是沒有糾結的必要，
參考：
[1]. 重學資料結構（序：概覽）
[2]. 劍指Offer——演算法復雜度中的O(logN)底數是多少
[3]. 如何理解演算法時間復雜度的表示法，例如 O(n2)、O(n)、O(1)、O(nlogn) 等？
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294942.html
標籤：其他