時間複雜度中的log(n)底數是多少?

2020-12-05 技術很有趣

其實這裡的底數對於研究程序運行效率不重要，寫代碼時要考慮的是數據規模n對程序運行效率的影響，常數部分則忽略，同樣的，如果不同時間複雜度的倍數關係為常數，那也可以近似認為兩者為同一量級的時間複雜度。

現在來看看為什麼底數具體為多少不重要？

讀者只需要掌握（依稀記得）中學數學知識就夠了。

假設有底數為2和3的兩個對數函數，如上圖。當X取N（數據規模）時，求所對應的時間複雜度得比值，即對數函數對應的y值，用來衡量對數底數對時間複雜度的影響。

比值為log2 N / log3 N，運用換底公式後得：(lnN/ln2) / (lnN/ln3) = ln3 / ln2，ln為自然對數，顯然這三個常數，與變量N無關。

用文字表述：算法時間複雜度為log（n）時，不同底數對應的時間複雜度的倍數關係為常數，不會隨著底數的不同而不同，因此可以將不同底數的對數函數所代表的時間複雜度，當作是同一類複雜度處理，即抽象成一類問題。

當然這裡的底數2和3可以用a和b替代，a，b大於等於2，屬於整數。a,b取值是如何確定的呢？

有點編程經驗的都知道，分而治之的概念。排序算法中有一個叫做「歸併排序」或者「合併排序」的算法，它用到的就是分而治之的思想，而它的時間複雜度就是N*logN，此算法採用的是二分法，所以可以認為對應的對數函數底數為2，也有可能是三分法，底數為3，以此類推。但是不可能我分數及負數。

說明：為了便於說明，本文時間複雜度一概省略 O 符號。

相關焦點

  • 編程中的數學公式 —— Log
    如果我沒記錯的話， 在大家計算時間複雜度和空間複雜度的時候，經常出現一個數學公式 Log。Log 對數在數學中，「對數」是對求冪的逆運算，正如除法是乘法的倒數，反之亦然。這意味著一個數字的對數是必須產生另一個固定數字（基數）的指數。
  • 對數log與指數函數的反函數
    (a) N .其中，a叫做對數的底數，N叫做真數。二,對數的運算性質如果a>0，且a≠1，M>0，N>0，那麼1.log(a)(MN)=log(a)M+log(a)N2.log(a)M^n=nlog(a)M（n∈R）3.log（a）M/N=log（a）M-log(a)N4.log(a^n)(b^m)=M/Nlog（a）b
  • 可能是最可愛的一文讀懂系列:皮卡丘の複雜度分析指南
    複雜度分析中的另一個重要概念是空間複雜度。顧名思義，它是指算法在N非常大的情況下佔用多少硬碟空間或內存。　　每當我們比較用於解決特定問題的各算法時，我們不僅僅關注時間複雜度，空間複雜度也是比較不同算法的重要方面。是的，可能目前我們的機器有大量可用內存，因此，多消耗些空間沒什麼影響。但是，我們不應該一直忽視它。
  • Excel函數公式大全之利用LOG函數計算指定正數值和底數的對數值
    今天我們依舊要學習的是Excel函數中的數學函數LOG函數。在學習LOG函數之前我們先了解一下什麼是對數公式。對數公式是數學中的一種常見公式，如果a^x=N(a>0,且a≠1)，則x叫做以a為底N的對數,記做x=log(a)(N)，其中a要寫於log右下。其中a叫做對數的底，N叫做真數 [1] 。通常我們將以10為底的對數叫做常用對數，以e為底的對數稱為自然對數。
  • Fibonacci 斐波那契數列的幾種寫法、時間複雜度對比
    用 Python 實現斐波那契數列常見的寫法有三種，各算法的執行效率也有很大差別，在面試中也會偶爾會被問到，通常面試的時候不是讓你簡單的用遞歸寫寫就完了，還會問你時間複雜度怎樣，空間複雜度怎樣，有沒有可改進的地方。
  • 用機器學習構建O(N)複雜度的排序算法,可在GPU和TPU上加速計算
    排序一直是計算機科學中最為基礎的算法之一，從簡單的冒泡排序到高效的桶排序，我們已經開發了非常多的優秀方法。但隨著機器學習的興起與大數據的應用，簡單的排序方法要求在大規模場景中有更高的穩定性與效率。中國科技大學和蘭州大學等研究者提出了一種基於機器學習的排序算法，它能實現 O(N) 的時間複雜度，且可以在 GPU 和 TPU 上高效地實現並行計算。
  • ...nlogn)時間、O(n)空間複雜度可微分排序算法,速度快出一個數量級
    排序，在計算機中是再常見不過的算法。在機器學習中，排序也經常用於統計數據、信息檢索等領域。那麼問題來了，排序算法在函數角度上是分段線性的，也就是說，在幾個分段的「節點」處是不可微的。這樣，就給反向傳播造成了困難。
  • ln三分之一等於多少 ln三分之一大於0嗎 - 天氣加
    ln(1/3)=-ln3=-log3^3/log3^e=-1/log3^e ^前為底數，後為真數。y=lnx這個函數是單調遞增的，3>e，e約等於2.718。因此根據函數的單調性可以知道ln3>lne，所以ln1/3+lne>0。
  • MySQL如何計算統計redo log大小
    在MySQL中如何計算、統計重做日誌（redo log)的生成情況呢？ 例如10分鐘內，生成了多少M的redo log呢?30分鐘內又生成了多少M的redo log.....。MySQL沒有像Oracle中那樣的系統視圖統計這些數據，但是我們可以通過一些方法曲線的統計二進位日誌的生成量。
  • n的階乘後面有多少個零?
    自然數n的階乘寫作n!。 即n!=1×2×3×...×(n-1)×n。階乘亦可以遞歸方式定義：0!=1，n!=(n-1)!×n。 給你一個非負整數n，要你計算階乘n!的結果末尾有幾個 0。比如說輸入n = 5，因為5! = 120，末尾有一個 0。 我們先來分析一下末尾的 0 從哪裡來的？
  • Excel函數公式大全之利用LOG10函數求任意以10為底數的對數值
    今天我們依舊要學習的是Excel函數中的數學函數LOG10函數。在上一節的課程中，大家已經對對數公式有了一定的了解了。今天我們要學習的LOG10函數，是計算任意正數值以10為底數的對數值。下面我們一起來了解一下LOG10函數的功能、語法以及參數解釋。
  • 七年級下冊數學:冪的運算之同底數冪的乘法解析(附基礎練習)
    +n）同底數冪相乘，底數不變，指數相加。現在我們就利用同底數冪相乘的運算法則來進行相關計算。例1、計算：分析：在同底數冪的運算中，底數可以用任意的數或代數式來代替，自然「負數的奇數次冪是負數，負數的偶數次冪是正數"要記牢。
  • 靈魂拷問:如何檢查 Java 數組中是否包含某個值?
    如何檢查數組（未排序）中是否包含某個值 ？這是一個非常有用並且經常使用的操作。我想大家的腦海中應該已經浮現出來了幾種解決方案，這些方案的時間複雜度可能大不相同。我先來提供四種不同的方法，大家看看是否高效。
  • 機器學習中各種熵的定義及理解
    在生活中，極少發生的事情最容易引起吃瓜群眾的關注。而經常發生的事情則不會引起注意，比如吃瓜群眾從來不會去關係明天太陽會不會東邊升起。也就是說，信息量的多少與事件發生概率的大小成反比。對於已發生的事件i，其所提供的信息量為：
  • 人教版數學八上預習①:同底數冪的乘法
    一、準備知識：乘方首先要複習下乘方的概念和基本計算，知道什麼是底數、指數，什麼是冪。a的n次方表示n個a相乘，其中a叫做底數，n叫做指數（底下的是底數，上面的是指數），整體合起來叫做冪。同底數冪就是底數相同，寫成乘方形式的幾個數，既可以是具體的數字，也可以用字母表示，如10^5和10^3，a^2、a^3和a^5。2、公式及推導推導過程課本上已經講得很詳細了，如果用文字描述就是：m個a乘上n個a一共是(m+n)個a。