一、定義
(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ù)。這樣能夠簡化算法分析,并且使注意力集中在最重要的一點(diǎn)上:增長率。
⑶ 用大Ο記號(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ì)于一些簡單的輸入輸出語句或賦值語句,近似認(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ù)雜度
您可能感興趣的文章:- C++實(shí)現(xiàn)的O(n)復(fù)雜度內(nèi)查找第K大數(shù)算法示例
- C++找出字符串中出現(xiàn)最多的字符和次數(shù),時(shí)間復(fù)雜度小于O(n^2)
- Java算法之時(shí)間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算
- 淺談Java如何實(shí)現(xiàn)一個(gè)基于LRU時(shí)間復(fù)雜度為O(1)的緩存
- Python算法中的時(shí)間復(fù)雜度問題
- php 常用算法和時(shí)間復(fù)雜度
- PHP 巧用數(shù)組降低程序的時(shí)間復(fù)雜度
- PHP 用數(shù)組降低程序的時(shí)間復(fù)雜度
- 淺談c++性能測(cè)試工具之計(jì)算時(shí)間復(fù)雜度