程序和算法的時(shí)間復(fù)雜度
1.一個(gè)程序或算法的時(shí)間效率，也稱“時(shí)間復(fù)雜度”肯适，有時(shí)簡(jiǎn)稱“復(fù)雜度”
2.復(fù)雜度常用大寫字母O和小寫字母n來(lái)表示望迎，比如O(n),O(n2)等，n代表問(wèn)題的規(guī)模
3.時(shí)間復(fù)雜度是用算法運(yùn)行過(guò)程中桐智，某種時(shí)間固定的操作需要被執(zhí)行的次數(shù)和n的關(guān)系來(lái)度量的末早，在無(wú)序數(shù)列中查找某個(gè)數(shù)，復(fù)雜度是O(n)
4.計(jì)算復(fù)雜度的時(shí)候说庭，只統(tǒng)計(jì)執(zhí)行次數(shù)最多的(n足夠大時(shí))那種固定操作的次數(shù)然磷，比如某個(gè)算法需要執(zhí)行加法n2次，除法n次刊驴，那么就記其復(fù)雜度是O(n2)
5.復(fù)雜度有“平均復(fù)雜度”和“最壞復(fù)雜度”兩種姿搜，兩者可能一致，也可能不一致
例如：順序查找捆憎，平均復(fù)雜度為n/2，最壞復(fù)雜度為n攻礼，復(fù)雜度都為O(n)，注意這里不計(jì)系數(shù)
快速排序礁扮，平均復(fù)雜度n*log n，最壞復(fù)雜度為n2
6.如果復(fù)雜度是多個(gè)n函數(shù)的和瞬沦，只關(guān)心隨n增長(zhǎng)增長(zhǎng)速度最快的那個(gè)函數(shù)
7.常見(jiàn)的大O運(yùn)行時(shí)間
O(log n)，對(duì)數(shù)級(jí)逛钻，包括二分查找
O(n)，線性級(jí)曙痘，包括簡(jiǎn)單查找即順序查找
O(n*log n)芳悲，線性對(duì)數(shù)級(jí)，快速排序
O(n2)名扛，平方級(jí)，選擇排序肮韧，冒泡排序融蹂，插入排序
O(na)弄企，多項(xiàng)式級(jí)超燃，基于n的a層循環(huán)
O(n!)，階乘級(jí)拘领，旅行商問(wèn)題
二分查找
例：
A有一個(gè)1～100的數(shù)意乓，B來(lái)猜，可以提問(wèn)院究，A只能回答對(duì)和錯(cuò)洽瞬，要以最少次數(shù)猜到這個(gè)數(shù)字
1.是1嗎？是2嗎业汰？伙窃。。样漆。是99嗎为障？平均要問(wèn)50次
2.大于50嗎？大于75嗎放祟？鳍怨。。跪妥。每次縮小范圍到一半鞋喇，7次以內(nèi)就能猜到
此時(shí)二分查找的簡(jiǎn)單程度顯而易見(jiàn)
簡(jiǎn)單查找時(shí)間復(fù)雜度為O(n)，二分查找時(shí)間復(fù)雜度為O(log n)
但請(qǐng)注意眉撵，二分查找前提條件是查找的數(shù)列必須是有序的
下面來(lái)寫一個(gè)程序描述上述過(guò)程：
最后提一下旅行商問(wèn)題
大概就是一個(gè)旅行商需要前往5個(gè)城市侦香，同時(shí)要確保旅程最短
為此，可以考慮前往這些城市的各種可能性
對(duì)于每種順序纽疟，他都計(jì)算總旅程罐韩，再挑選出旅程最短的線路
顯然，5個(gè)城市有5污朽！=120種不同的排列方式
推而廣之散吵，n個(gè)城市需要執(zhí)行n！次操作才能計(jì)算出結(jié)果
因此運(yùn)行時(shí)間為O(n!)，這種算法時(shí)間復(fù)雜度非常糟糕
