1.定義

(1)基本執(zhí)行次數(shù)函數(shù)T

一般情況下算法基本操作的執(zhí)行次數(shù)是關(guān)于n的某個(gè)函數(shù)，記做T(n)。

(2)同數(shù)量級函數(shù)

如果現(xiàn)在有一個(gè)關(guān)于n的輔助函數(shù)f(n)，使得當(dāng)n趨于無窮大時(shí)，T(n)/f(n)的極限值為一個(gè)不等于0的常熟，則稱f(n)是T(n)的同數(shù)量級函數(shù)，記做T(n)=O(f(n))。

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

O是用來表示數(shù)量級的符號。O(f(n))就是算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。

2.常見算法復(fù)雜度

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

3.如何計(jì)算算法時(shí)間復(fù)雜度

找到運(yùn)行次數(shù)最多的語句，計(jì)算語句執(zhí)行次數(shù)的數(shù)量級，用O(f(n))表示。

4.NP問題

Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項(xiàng)式時(shí)間，而Ο(2n)和Ο(n!)稱為指數(shù)時(shí)間。計(jì)算機(jī)科學(xué)家普遍認(rèn)為前者是有效算法，把這類問題稱為P類問題，而把后者稱為NP問題。