大 O 復(fù)雜度表示法
- 假設(shè)每行代碼執(zhí)行的時(shí)間都是一樣的铣缠。為 unit_time
- 所有代碼的執(zhí)行時(shí)間T(n)與每行代碼的執(zhí)行次數(shù)n成正比
- 大O公式 T(n) = O(fn)
- 公式講解: T(n) 我們已經(jīng)講話了，它表示代碼執(zhí)行的時(shí)間。n表示數(shù)據(jù)規(guī)模的大小弓柱。f(n)表示每行代碼執(zhí)行的次數(shù)總和蒸播。公式中的O表示代碼的執(zhí)行時(shí)間T(n)與f(n)表達(dá)式成正比枢劝。
- 大O時(shí)間復(fù)雜度表示法，大O時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間疑枯，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢。所以也叫漸進(jìn)時(shí)間負(fù)責(zé)度蛔六。 簡稱時(shí)間復(fù)雜度荆永。
- 當(dāng)n很大時(shí)，你可以把它想象成 10000国章、100000具钥。而公式中的低階系數(shù)三部分并不左右增長趨勢，所以都可以忽略捉腥。我們只需要記錄一一個(gè)最大量級就可以了氓拼，如果用大 O 表示法表示剛講的那兩段代的時(shí)間復(fù)雜度，就可以記為：T(n) = O(n)抵碟； T(n) = O(n2)桃漾。
時(shí)間復(fù)雜度分析
只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
在分析一個(gè)算法，一段代碼的時(shí)間復(fù)雜度的時(shí)候拟逮，也只關(guān)注循環(huán)次數(shù)執(zhí)行最多的那一段代碼就可以了撬统。這段核心代碼執(zhí)行次數(shù)的n的量級 就是整段代碼要分析的時(shí)間復(fù)雜度-
加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
我們可以分別分析每一部分的時(shí)間復(fù)雜度，然后把它們放到一塊兒敦迄，再取一個(gè)量級最大的作為整段代碼的復(fù)雜度恋追。
只要是一個(gè)已知的數(shù)，跟n無關(guān)罚屋，照樣也是常量級的執(zhí)行時(shí)間苦囱。
時(shí)間復(fù)雜度的概念來說 它表示的是一個(gè)算法執(zhí)行效率與數(shù)據(jù)規(guī)模增長的變化趨勢。所以不管常量的執(zhí)行時(shí)間多大脾猛，我們都可以忽略掉撕彤。因?yàn)樗旧韺υ鲩L趨勢沒有影響∶退總的時(shí)間復(fù)雜度就等于量級最大的那段代碼的時(shí)間復(fù)雜度 -
乘法法則:嵌套代碼的復(fù)雜度等于前套內(nèi)外代碼復(fù)雜度的乘積羹铅。
我們可以把乘法法則看成是嵌套循環(huán)
- 為了表示在不同情況下的不同時(shí)間復(fù)雜度。引入三個(gè)概念：
- 最好情況時(shí)間復(fù)雜度
- 最壞情況時(shí)間復(fù)雜度
- 平均情況時(shí)間復(fù)雜度
- 平均情況時(shí)間復(fù)雜度
- 也加做加權(quán)平均時(shí)間復(fù)雜度或者期望時(shí)間復(fù)雜度
- 均攤時(shí)間復(fù)雜度 -- 均還分析(平攤分析)
- 盡管很多數(shù)據(jù)結(jié)構(gòu)和算法書籍都花了很大力氣來區(qū)分平均時(shí)間復(fù)雜度和均攤時(shí)間復(fù)雜度.均攤時(shí)間復(fù)雜度就是一種特殊的平均時(shí)間復(fù)雜度愉昆。
