一、復(fù)雜度分析的4個(gè)概念

1.最壞情況時(shí)間復(fù)雜度：代碼在最理想情況下執(zhí)行的時(shí)間復(fù)雜度。
2.最好情況時(shí)間復(fù)雜度：代碼在最壞情況下執(zhí)行的時(shí)間復(fù)雜度。
舉例:遍歷一個(gè)長(zhǎng)度為n的數(shù)組,查找某個(gè)值,查到了就退出.那么最壞情況時(shí)間復(fù)雜度就是O(n),最好情況時(shí)間復(fù)雜度就是O(1)

3.平均時(shí)間復(fù)雜度：用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示。
4.均攤時(shí)間復(fù)雜度：在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級(jí)別的復(fù)雜度，個(gè)別情況是高級(jí)別復(fù)雜度且發(fā)生具有時(shí)序關(guān)系時(shí)，可以將個(gè)別高級(jí)別復(fù)雜度均攤到低級(jí)別復(fù)雜度上。基本上均攤結(jié)果就等于低級(jí)別復(fù)雜度。

舉例:有一個(gè)長(zhǎng)度為n的數(shù)組,如果數(shù)組沒(méi)滿,就往里插入一個(gè)數(shù),如果數(shù)組滿了,就遍歷求和.那么絕大多數(shù)情況下都是O(1),只有最后一次是O(n),均攤以后就是O(1)

二、為什么要引入這4個(gè)概念？

1.同一段代碼在不同情況下時(shí)間復(fù)雜度會(huì)出現(xiàn)量級(jí)差異，為了更全面，更準(zhǔn)確的描述代碼的時(shí)間復(fù)雜度，所以引入這4個(gè)概念。
2.代碼復(fù)雜度在不同情況下出現(xiàn)量級(jí)差別時(shí)才需要區(qū)別這四種復(fù)雜度。大多數(shù)情況下，是不需要區(qū)別分析它們的。

三、如何分析平均、均攤時(shí)間復(fù)雜度？

1.平均時(shí)間復(fù)雜度
代碼在不同情況下復(fù)雜度出現(xiàn)量級(jí)差別，則用代碼所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。
2.均攤時(shí)間復(fù)雜度
兩個(gè)條件滿足時(shí)使用：1）代碼在絕大多數(shù)情況下是低級(jí)別復(fù)雜度，只有極少數(shù)情況是高級(jí)別復(fù)雜度；2）低級(jí)別和高級(jí)別復(fù)雜度出現(xiàn)具有時(shí)序規(guī)律。均攤結(jié)果一般都等于低級(jí)別復(fù)雜度。