（*useful）標(biāo)記：目前覺(jué)得有用的函數(shù)
//FIXME 標(biāo)記：待補(bǔ)充

基本初等函數(shù):

• 冪函數(shù)：

一般地，形如y=x^α(α為有理數(shù)）的函數(shù)，即以底數(shù)為自變量，冪為因變量，指數(shù)為常數(shù)的函數(shù)稱為冪函數(shù)。例如函數(shù)y=x⁰ 、y=x¹、y=x²、y=x^-1（注：y=x^-1=1/x y=x⁰時(shí)x≠0）等都是冪函數(shù)。一般形式如下：

（ α為常數(shù)，且可以是自然數(shù)、有理數(shù)，也可以是任意實(shí)數(shù)或復(fù)數(shù)。）
有理數(shù)： （正整數(shù)、0、負(fù)整數(shù)）和（正分?jǐn)?shù)，負(fù)分?jǐn)?shù)）的統(tǒng)稱

• 指數(shù)函數(shù):

指數(shù)函數(shù)是數(shù)學(xué)中重要的函數(shù)。應(yīng)用到值e上的這個(gè)函數(shù)寫為exp(x)。還可以等價(jià)的寫為e^x，這里的e是數(shù)學(xué)常數(shù)，就是自然對(duì)數(shù)的底數(shù)，近似等于 2.718281828，還稱為歐拉數(shù)。一般形式如下：

指數(shù)函數(shù)

• 對(duì)數(shù)函數(shù):

一般地，函數(shù)y=log_ax（a>0，且a≠1）叫做對(duì)數(shù)函數(shù)，也就是說(shuō)以冪（真數(shù)）為自變量，指數(shù)為因變量，底數(shù)為常量的函數(shù)，叫對(duì)數(shù)函數(shù)。

其中x是自變量，函數(shù)的定義域是（0，+∞），即x>0。它實(shí)際上就是指數(shù)函數(shù)的反函數(shù)，可表示為x=a^y。因此指數(shù)函 數(shù)里對(duì)于a的規(guī)定，同樣適用于對(duì)數(shù)函數(shù)。一般形式如下:

（a>0, a≠1， x>0,特別當(dāng)α=e時(shí)，記為y=ln x）

時(shí)間復(fù)雜度

（一）時(shí)間頻度

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。
一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(n)。

（二）時(shí)間復(fù)雜度

在剛才提到的時(shí)間頻度中，n稱為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此，我們引入時(shí)間復(fù)雜度概念。
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度 ，簡(jiǎn)稱時(shí)間復(fù)雜度。

符號(hào)O ：Landau符號(hào)的作用在于用簡(jiǎn)單的函數(shù)來(lái)描述復(fù)雜函數(shù)行為，給出一個(gè)上或下（確）界：
某個(gè)算法的時(shí)間復(fù)雜度是 O(1)， 常數(shù)階， 優(yōu)秀 。
某個(gè)算法的時(shí)間復(fù)雜度是 O(log₂ n)，對(duì)數(shù)階， 良好 。
某個(gè)算法的時(shí)間復(fù)雜度是 O(n)， 線性.次線性階，還好。
某個(gè)算法的時(shí)間復(fù)雜度是 O(n log₂ n)，線性對(duì)數(shù)階， 還不錯(cuò)。
某個(gè)算法的時(shí)間復(fù)雜度是 O(n²)， 平方階， 差一些 。
（*useful）

（三）求解算法的時(shí)間復(fù)雜度的具體步驟是

（1） 找出算法中的基本語(yǔ)句；
　　算法中執(zhí)行次數(shù)最多的那條語(yǔ)句就是基本語(yǔ)句，通常是最內(nèi)層循環(huán)的循環(huán)體。
（2） 計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)；
　　只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。
（3）用大Ο記號(hào)表示算法的時(shí)間性能。
　　將基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中。

如果算法中包含嵌套的循環(huán)，則基本語(yǔ)句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時(shí)間復(fù)雜度相加。例如：

  for (i=1; i<=n; i++) {
        x++;  
  }
  for (i=1; i<=n; i++)  {
      for (j=1; j<=n; j++)  {
            x++;  
      }
}

第一個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n)，第二個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n²)，則整個(gè)算法的時(shí)間復(fù)雜度為Ο(n+n²)=Ο(n²)。

（*useful）
Ο(1): 表示基本語(yǔ)句的執(zhí)行次數(shù)是一個(gè)常數(shù)，一般來(lái)說(shuō)，只要算法中不存在循環(huán)語(yǔ)句，其時(shí)間復(fù)雜度就是Ο(1)。
多項(xiàng)式時(shí)間: O(log₂n)、Ο(n)、 Ο(n log₂n)、Ο(n²)和Ο(n³) 。 (推薦)
指數(shù)時(shí)間: Ο(2ⁿ)和Ο(n!) 。

（四）下面分別對(duì)幾個(gè)常見(jiàn)的時(shí)間復(fù)雜度進(jìn)行示例說(shuō)明

(1)、O(1)

        Temp=i; i=j; j=temp;        

以上三條單個(gè)語(yǔ)句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。注意：如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)。

(2)、O(n²)

2.1. 交換i和j的內(nèi)容

 sum=0；                 （一次）  
 for(i=1;i<=n;i++)     （n+1次）  
     for(j=1;j<=n;j++) （n2次）  
         sum++；            （n2次）  

解：因?yàn)棣?2n²+n+1)=n²（Θ即：去低階項(xiàng)，去掉常數(shù)項(xiàng)，去掉高階項(xiàng)的常參得到），所以T(n)= =O(n²)；

2.2.

 for (i=1;i<n;i++)  
  {   
      y=y+1;         ①     
      for (j=0;j<=(2*n);j++)      
            x++;         ②        
  }            

解：
語(yǔ)句1的頻度是n-1
語(yǔ)句2的頻度是(n-1)(2n+1) = 2n²-n-1
f(n)=2n²-n-1+(n-1) = 2n²-2；

又Θ(2n²-2)=n²
該程序的時(shí)間復(fù)雜度T(n)=O(n²).

一般情況下，對(duì)步進(jìn)循環(huán)語(yǔ)句只需考慮循環(huán)體中語(yǔ)句的執(zhí)行次數(shù)，忽略該語(yǔ)句中步長(zhǎng)加1、終值判別、控制轉(zhuǎn)移等成分，當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的。

(3)、O(n)

  a=0;  
    b=1;                      ①  
      for (i=1;i<=n;i++) ②  
      {    
        s=a+b;　　　?、? 
        b=a;　　　　?、?   
        a=s;　　　　　⑤  
     }  

解： 語(yǔ)句1的頻度：2,
語(yǔ)句2的頻度： n,
語(yǔ)句3的頻度： n-1,
語(yǔ)句4的頻度：n-1,
語(yǔ)句5的頻度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

(4)、O(log₂n)

  i=1;     ①  
  while (i<=n)  
      i=i*2; ②  

解： 語(yǔ)句1的頻度是1,
設(shè)語(yǔ)句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=log₂n
取最大值f(n)=log₂n,
T(n)=O(log₂n)

(5)、O(n³)

 for(i=0;i<n;i++)  
  {    
    for(j=0;j<i;j++)    
    {  
      for(k=0;k<j;k++)  
      x=x+2;    
    }  
  }  

解：當(dāng)i=m, j=k的時(shí)候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí), j 可以取 0,1,...,m-1 , 所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環(huán)共進(jìn)行了:0+(1-1)1/2+...+(n-1)n/2=n(n+1)(n-1)/6
所以時(shí)間復(fù)雜度為O(n³).

（五）常用的算法的時(shí)間復(fù)雜度和空間復(fù)雜度

這里討論的是內(nèi)部排序

swift寫的部分算法實(shí)現(xiàn)鏈接

算法時(shí)間復(fù)雜度分析是一個(gè)很重要的問(wèn)題，任何一個(gè)程序員都應(yīng)該熟練掌握其概念和基本方法，而且要善于從數(shù)學(xué)層面上探尋其本質(zhì)，才能準(zhǔn)確理解其內(nèi)涵。

空間復(fù)雜度

類似于時(shí)間復(fù)雜度的討論，一個(gè)算法的空間復(fù)雜度(Space Complexity)S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。

空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。
一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括:

1. 存儲(chǔ)算法本身所占用的存儲(chǔ)空間
   • 與算法書寫的長(zhǎng)短成正比，要壓縮這方面的存儲(chǔ)空間，就必須編寫出較短的算法。
2. 算法的輸入輸出數(shù)據(jù)所占用的存儲(chǔ)空間
   • 由要解決的問(wèn)題決定，是通過(guò)參數(shù)表由調(diào)用函數(shù)傳遞而來(lái)的，它不隨本算法的不同而改變。
3. 算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間
   • 隨算法的不同而異，有的算法只需要占用少量的臨時(shí)工作單元，而且不隨問(wèn)題規(guī)模的大小而改變，我們稱這種算法是“就地"進(jìn)行的，跟語(yǔ)言C，swift，js：對(duì)象開(kāi)辟內(nèi)存函數(shù)有關(guān)
   • 有的算法需要占用的臨時(shí)工作單元數(shù)與解決問(wèn)題的規(guī)模n有關(guān)，它隨著n的增大而增大，當(dāng)n較大時(shí)，將占用較多的存儲(chǔ)單元

• 當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)，可表示為O(1)；
• 當(dāng)一個(gè)算法的空間復(fù)雜度與以2為底的n的對(duì)數(shù)成正比時(shí)，可表示為0(log₂n)；
• 當(dāng)一個(gè)算法的空I司復(fù)雜度與n成線性比例關(guān)系時(shí)，可表示為0(n);
• 若形參為數(shù)組，則只需要為它分配一個(gè)存儲(chǔ)由實(shí)參傳送來(lái)的一個(gè)地址指針的空間，即一個(gè)機(jī)器字長(zhǎng)空間；
• 若形參為引用方式，則也只需要為其分配存儲(chǔ)一個(gè)地址的空間，用它來(lái)存儲(chǔ)對(duì)應(yīng)實(shí)參變量的地址，以便由系統(tǒng)自動(dòng)引用實(shí)參變量。

swift寫的部分算法playground->github