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

1、時(shí)間復(fù)雜度計(jì)算學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，覺得時(shí)間復(fù)雜度計(jì)算很復(fù)雜，怎么也看不懂，差不多三年之后，還是不懂，馬上就要找工作了，趕緊惡補(bǔ)一下吧：首先了解一下幾個(gè)概念。一個(gè)是時(shí)間復(fù)雜度，一個(gè)是漸近時(shí)間復(fù)雜度。前者是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。當(dāng)我們?cè)u(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度，因此，在算法分析時(shí)，往往對(duì)兩者不予區(qū)分，經(jīng)常是將漸近時(shí)間復(fù)雜度

2、T(n)=O(f(n))簡稱為時(shí)間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。此外，算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。但是我們總是考慮在最壞的情況下的時(shí)間復(fù)雜度。以保證算法的運(yùn)行時(shí)間不會(huì)比它更長。常見的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、k次方階O(n^k)、指數(shù)階O(