一、定義

（1）如果一個(gè)問題的規(guī)模是n，解這一問題的某一算法所需要的時(shí)間為T(n)，它是n的某一函數(shù) T(n)稱為這一算法的“時(shí)間復(fù)雜性”。我們常用大O表示法表示時(shí)間復(fù)雜性，稱之為大O記法。
（2）一個(gè)問題本身也有它的復(fù)雜性，如果某個(gè)算法的復(fù)雜性到達(dá)了這個(gè)問題復(fù)雜性的下界，那就稱這樣的算法是最佳算法。常見的時(shí)間復(fù)雜度高低順序如下：
O(1) 常數(shù)階 < O(logn) 對(duì)數(shù)階 < O(n) 線性階 < O(nlogn) < O(n^2) 平方階 < O(n^3) < O(2^n) < O(n!) < O(n^n)

二、時(shí)間復(fù)雜度計(jì)算步驟

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

三、時(shí)間復(fù)雜度計(jì)算規(guī)則

（1）對(duì)于一些簡(jiǎn)單的輸入輸出語句或賦值語句,近似認(rèn)為需要O(1)時(shí)間
（2）對(duì)于順序結(jié)構(gòu),需要依次執(zhí)行一系列語句所用的時(shí)間可采用大O下"求和法則"
求和法則:是指若算法的2個(gè)部分時(shí)間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))
特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))
（3）對(duì)于選擇結(jié)構(gòu),如if語句,它的主要時(shí)間耗費(fèi)是在執(zhí)行then字句或else字句所用的時(shí)間,需注意的是檢驗(yàn)條件也需要O(1)時(shí)間
（4）對(duì)于循環(huán)結(jié)構(gòu),循環(huán)語句的運(yùn)行時(shí)間主要體現(xiàn)在多次迭代中執(zhí)行循環(huán)體以及檢驗(yàn)循環(huán)條件的時(shí)間耗費(fèi),一般可用大O下"乘法法則"
乘法法則: 是指若算法的2個(gè)部分時(shí)間復(fù)雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1*T2=O(f(n)*g(n))
（5）對(duì)于復(fù)雜的算法,可以將它分成幾個(gè)容易估算的部分,然后利用求和法則和乘法法則技術(shù)整個(gè)算法的時(shí)間復(fù)雜度

最新評(píng)論