程序和算法的時(shí)間復(fù)雜度

1.一個(gè)程序或算法的時(shí)間效率，也稱“時(shí)間復(fù)雜度”，有時(shí)簡(jiǎn)稱“復(fù)雜度”

2.復(fù)雜度常用大寫字母O和小寫字母n來表示，比如O(n),O(n2)等，n代表問題的規(guī)模

3.時(shí)間復(fù)雜度是用算法運(yùn)行過程中，某種時(shí)間固定的操作需要被執(zhí)行的次數(shù)和n的關(guān)系來度量的，在無序數(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.常見的大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í)，旅行商問題

二分查找

例：
A有一個(gè)1～100的數(shù)，B來猜，可以提問，A只能回答對(duì)和錯(cuò)，要以最少次數(shù)猜到這個(gè)數(shù)字

1.是1嗎？是2嗎？。。。是99嗎？平均要問50次
2.大于50嗎？大于75嗎？。。。每次縮小范圍到一半，7次以內(nèi)就能猜到

此時(shí)二分查找的簡(jiǎn)單程度顯而易見
簡(jiǎn)單查找時(shí)間復(fù)雜度為O(n)，二分查找時(shí)間復(fù)雜度為O(log n)
但請(qǐng)注意，二分查找前提條件是查找的數(shù)列必須是有序的
下面來寫一個(gè)程序描述上述過程：

最后提一下旅行商問題

大概就是一個(gè)旅行商需要前往5個(gè)城市，同時(shí)要確保旅程最短
為此，可以考慮前往這些城市的各種可能性
對(duì)于每種順序，他都計(jì)算總旅程，再挑選出旅程最短的線路
顯然，5個(gè)城市有5！=120種不同的排列方式
推而廣之，n個(gè)城市需要執(zhí)行n！次操作才能計(jì)算出結(jié)果
因此運(yùn)行時(shí)間為O(n!)，這種算法時(shí)間復(fù)雜度非常糟糕