算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，而空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

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

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 n 的某個(gè)函數(shù)，用T(n)表示。若存在函數(shù) f(n)，使得當(dāng) n 趨近于無窮大時(shí)，T(n) / f(n) 的極限值（當(dāng) n 趨近于無窮大時(shí)）為非零常數(shù)，則稱 f(n) 是 T(n) 的同數(shù)量級(jí)函數(shù)。記作 T(n) = O(f(n))，稱 O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

隨著問題規(guī)模 n 的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率成正比，所以 f(n) 越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。

時(shí)間復(fù)雜度計(jì)算

在計(jì)算時(shí)間復(fù)雜度的時(shí)候，首先需要找出算法的基本操作，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)，再找出 T(n) 的同數(shù)量級(jí)（包括： $1, \log_2n，n，n \log_2n ，n^2，n^3，2^n，n!$ 等），找出后，f(n) = 該數(shù)量級(jí)，若 T(n) / f(n) 求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度 T(n) = O(f(n))。

$O(1)$ ：常數(shù)復(fù)雜度（Constant Complexity）

n = 1000
print(n)

$O(log(n))$ ：對(duì)數(shù)復(fù)雜度（Logarithmic Complexity）

i = 1
n = 1000
while i < n:
  print(i)
  i = i * 2 # 終止條件為對(duì)數(shù)

$O(n)$ ：線性復(fù)雜度（Linear Complexity）

n = 1000
for i in range(n):
  print(i)

$O(n^2)$ ：平方復(fù)雜度（N Square Complexity）

n = 1000
for i in range(n):
  for j in range(n):
    print(i+j)

$O(n^3)$ ：立方復(fù)雜度（N Cube Complexity）

n = 1000
for i in range(n):
  for j in range(n):
    for k in range(n):
      print(i+j+k)

$O(2^n)$ ：指數(shù)復(fù)雜度（Exponential Growth）

import math

i = 1
n = 1000
while i < math.pow(2,n): # 終止條件為指數(shù)
  print(i)

$O(n!)$ ：階乘復(fù)雜度（Factorial Complexity）

i = 1
n = 1000
while i < factorial(n): # 終止條件為指數(shù)
  print(i)

def factorial(n):
  if n == 0 or n == 1:
      return 1
  else:
      return (n * factorial(n - 1))

從以上實(shí)例中可以簡(jiǎn)單理解為，時(shí)間復(fù)雜度就是看代碼中復(fù)雜度最高部分的運(yùn)算次數(shù)，那么由小到大分別為：
$O(1)<O(log(n))<O(n)<O(n(log(n)))<O(n^2)<O(2^n)<O(n!)$

舉一個(gè)算法優(yōu)化的例子，假設(shè)我們需要將數(shù)字從 1 加到 n，如果使用循環(huán)，那么時(shí)間復(fù)雜度為 $O(n)$ ：

# 硬循環(huán)
n = 1000
y = 1 + 2 + 3 + ... + n
# for循環(huán)
y = 0
for i in range(n):
  y += i

如果利用等差數(shù)列求和公式：n(n + 1) / 2，時(shí)間復(fù)雜度可以降為 $O(1)$ ：

y = n * (n + 1) / 2

完整公式如下：
$S_n=na_1+\frac{n(n-1)}{2}d,n\in N^*$

其中 $a_1$ 為首項(xiàng)， $a_n$ 為末項(xiàng)， $n$ 為項(xiàng)數(shù)， $d$ 為公差， $S_n$ 為前 $n$ 項(xiàng)和。

求解斐波拉契數(shù)組（Fibonacci Array）：根據(jù)公式 $F_n = F_{n-1} + F_{n-2}$ 每個(gè)數(shù)字等于前兩個(gè)數(shù)字之和，如：1,1,2,3,5,8,13,21,34,... 求位置為 n 的數(shù)字。

遞歸實(shí)現(xiàn)如下：

def fib(n):
  if n == 0 or n == 1:
    return n
  return fib(n - 1) + fib(n - 2)

雖然代碼簡(jiǎn)單但是我們分析一下，它在計(jì)算每個(gè)位置的數(shù)字時(shí)，之前的數(shù)字都要重新計(jì)算一遍，復(fù)雜度是呈指數(shù)級(jí)增長(zhǎng)的，所以是 2 的 n 次方的時(shí)間復(fù)雜度，即 $O(2^n)$ 。

根據(jù)主定理（Master Theorem）推斷出常用算法的時(shí)間復(fù)雜度如下：

常用算法	時(shí)間復(fù)雜度
二分查找（Binary Search）	$O(log(n))$
二叉樹查找（Binary Tree Traversal）	$O(n)$
最優(yōu)有序矩陣查找（Optimal Sorted Matrix Search）	$O(n)$

通用數(shù)據(jù)結(jié)構(gòu)操作

數(shù)組排序算法

空間復(fù)雜度

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，類似時(shí)間復(fù)雜度，它也是問題規(guī)模 n 的函數(shù)，記做 S(n) = O(f(n))。比如直接插入排序（Straight Insertion Sort）的時(shí)間復(fù)雜度是 $O(n^2)$ ，空間復(fù)雜度是 $O(1)$ 。一般的遞歸算法的空間復(fù)雜度是 $O(n)$ ，因?yàn)槊看芜f歸都要存儲(chǔ)返回信息。

時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的。當(dāng)追求一個(gè)較好的時(shí)間復(fù)雜度時(shí)，可能會(huì)使空間復(fù)雜度的性能變差。反之，當(dāng)追求一個(gè)較好的空間復(fù)雜度時(shí)，可能會(huì)使時(shí)間復(fù)雜度的性能變差。另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當(dāng)設(shè)計(jì)一個(gè)算法時(shí)，要綜合考慮算法的各項(xiàng)性能，包括算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語言的特性、算法運(yùn)行的機(jī)器系統(tǒng)環(huán)境等各方面因素，才能夠設(shè)計(jì)出比較好的算法。

參考

https://time.geekbang.org/course/intro/130
https://book.douban.com/subject/3351237/

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

算法的復(fù)雜度

算法的復(fù)雜度

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