符號的含義：

https://blog.csdn.net/qq_39745932/article/details/82747191

Θ等于的意思。

Ο表示上界，小于等于的意思。

ο表示上界，小于的意思。

Ω表示下界，大于等于的意思。

ω表示下界，大于的意思。

O(1),O(n),O(logn),O(nlogn)的區(qū)別。

O(1):無論數(shù)據(jù)多大,一次可以找到目標，空間和時間一樣；

O(n):需要查找n次,才能確定目標，空間和時間一樣；

O(logn):數(shù)據(jù)增大n倍時,耗時logn次才能確定目標，空間增大,時間相對減少；

O(nlogn):數(shù)據(jù)增大n倍時,耗時n x logn倍才能確定目標,空間增大,時間也會加長。

logN的底數(shù)

1、如果a(a>0，且a≠1)的b次冪等于N，即a^b=N，那么數(shù)b叫做以a為底N的對數(shù)，記作：logaN=b,其中a叫做對數(shù)的底數(shù)，N叫做真數(shù)。

2、以10為底的對數(shù)叫常用對數(shù)，記作log10N，簡記為lgN；

3、以無理數(shù)e(e=2.718 28…)為底的對數(shù)叫做自然對數(shù)，記作logeN，簡記為lnN。

log不寫底數(shù)的時候，有默認的底數(shù)，物理上常用e，編程語言中Math.log常用e。

一般數(shù)學計算中常用10，數(shù)學學科里面的規(guī)矩，通通都是e，特別是在數(shù)論里面，基本上不用ln，都用log。

編程比賽OI中一般都是以2為底，計算時間復雜度的時候一般是默認log2。

在計算時間復雜度的時候，你會發(fā)現(xiàn)log的底數(shù)并不重要，底數(shù)的巨大變化并不會帶來結果上的數(shù)量級變化。

現(xiàn)在來看看為什么底數(shù)具體為多少不重要？

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

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

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

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

有點編程經(jīng)驗的都知道，分而治之的概念。排序算法中有一個叫做“歸并排序”或者“合并排序”的算法，它用到的就是分而治之的思想，而它的時間復雜度就是N*logN，此算法采用的是二分法，所以可以認為對應的對數(shù)函數(shù)底數(shù)為2，也有可能是三分法，底數(shù)為3，以此類推。

但是不可能是分數(shù)或者負數(shù)。