時(shí)間復(fù)雜度
在數(shù)據(jù)結(jié)構(gòu)和算法中您访，有兩種方法來衡量時(shí)間復(fù)雜度
- 事后統(tǒng)計(jì)法
- 大O復(fù)雜度表示法
事后統(tǒng)計(jì)法
把代碼實(shí)際跑一遍季二，然后分析狐粱，統(tǒng)計(jì)和監(jiān)控算法執(zhí)行的時(shí)間和占用的內(nèi)存大小伞剑。但是這種方法有很大的局限性
- 測(cè)試結(jié)果非常依賴測(cè)試環(huán)境：
測(cè)試環(huán)境的硬件不同會(huì)對(duì)結(jié)果有很大的影響斑唬，比如相同的代碼在不同的處理器結(jié)果肯定不同 - 測(cè)試結(jié)果受測(cè)試數(shù)據(jù)的規(guī)模大小的影響：
比如對(duì)同一個(gè)排序算法，待排序數(shù)據(jù)的有序度不一樣黎泣，排序的執(zhí)行時(shí)間就會(huì)有很大的差別恕刘。另外，如果測(cè)試數(shù)據(jù)過小抒倚，也可能無法真是反應(yīng)算法的性能褐着，比如對(duì)于小規(guī)模的數(shù)據(jù)排序，插入排序可能反倒比快速排序要快
大O時(shí)間復(fù)雜度表示法
時(shí)間復(fù)雜度的分析方法：
- 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
- 加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼的復(fù)雜度
- 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
常見的時(shí)間復(fù)雜度分析
常見復(fù)雜度分析
復(fù)雜度的量級(jí)有可以分為 多項(xiàng)式量級(jí) 和 非多項(xiàng)式量級(jí)
- 非多項(xiàng)式量級(jí)：O(2^n) 和 O(n!)托呕，非常低效的算法含蓉，執(zhí)行時(shí)間會(huì)隨數(shù)據(jù)的規(guī)模急劇增加
- 多項(xiàng)式量級(jí)：剩下的
1. O(1)
一般情況下，只要算法的代碼中项郊，不存在循環(huán)語句馅扣，遞歸，即使代碼有很多着降，時(shí)間復(fù)雜度也是O(1)
O(logn), O(nlogn)
在采用大O復(fù)雜度分析的情況下差油，可以忽略系數(shù)，比如 O(Cf(n)) = O(f(n))
O(m+n), O(m*n)
因?yàn)閙鹊碍，n兩個(gè)數(shù)據(jù)規(guī)模厌殉，我們無法評(píng)估誰的規(guī)模比較大酱讶，所有我們不能省略某一個(gè)
空間復(fù)雜度
常見的空間復(fù)雜度有 O(1),O(n),O(n2),O(logn),O(nlogn)适肠。空間復(fù)雜度相對(duì)比較簡(jiǎn)單容贝，而且一般使用到的都是O(1),O(n),O(n2)耀销。
復(fù)雜度比較分析
復(fù)雜度比較
