CS基礎(chǔ)：算法時(shí)間復(fù)雜度
此篇為大話數(shù)據(jù)結(jié)構(gòu)的筆記之一帖世，涉及到編碼的部分采用 Swift 最新版本來(lái)進(jìn)行編程笨奠。序比較亂假夺，幾乎屬于想到啥查啥寫啥涧衙。
時(shí)間復(fù)雜度
算法分析中的一個(gè)名詞哪工，即輸入到輸出經(jīng)過(guò)這個(gè)算法所經(jīng)歷的時(shí)間。
語(yǔ)句總的執(zhí)行次數(shù) T(n)是關(guān)于問(wèn)題規(guī)模 n 的函數(shù)弧哎，勁兒分析 T(n) 隨著 n 的變化情況并確定 T(n) 的數(shù)量級(jí)雁比。T(n) = O（f（n）），這個(gè)公式表示隨著問(wèn)題規(guī)模 n 的增大撤嫩，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同偎捎，f（n）是問(wèn)題規(guī)模 n 的某個(gè)函數(shù)。這種時(shí)間復(fù)雜度的記法稱為大 O 記法序攘。
最優(yōu)算法：隨著規(guī)模 n 的增大茴她，T(n)增長(zhǎng)最慢的算法。
推導(dǎo)大 O 階方法
基本原則：
- 用常數(shù) 1 取代運(yùn)行時(shí)間中的所有加法常數(shù)程奠。
- 在修改后的運(yùn)行次數(shù)函數(shù)中丈牢，只保留最高階項(xiàng)。
- 如果最高項(xiàng)存在且不是1瞄沙，則去除與這個(gè)項(xiàng)相乘的常數(shù)己沛。
經(jīng)過(guò)三步得到的結(jié)果就是大 O 階段。
常數(shù)階
高斯算法：
var sum = 0,n = 100 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
print(sum) //執(zhí)行一次
包括打印結(jié)果距境，這個(gè)算法的運(yùn)行次數(shù)函數(shù) f(n) = 3申尼。推導(dǎo)第一步，將常數(shù)3變成1垫桂。沒(méi)有最高階項(xiàng)师幕，所以這個(gè)算法的復(fù)雜度為 O(1)。
增加理解伪货，看下面這段代碼：
var sum = 0,n = 100 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
sum = (1 + n) * n / 2 //執(zhí)行一次
print(sum) //執(zhí)行一次
無(wú)論 n 為多少们衙，這兩段代碼的執(zhí)行結(jié)果相同，區(qū)別只是固定的執(zhí)行次數(shù)（循環(huán)結(jié)構(gòu)除外）碱呼，與 n 無(wú)關(guān)蒙挑，所以復(fù)雜度還是 O(1)。
線性階
for i in 0 ... n{
//執(zhí)行時(shí)間復(fù)雜度為O（1）的算法
}
循環(huán)體中代碼要執(zhí)行 n 次愚臀，時(shí)間復(fù)雜度 O（n）忆蚀，沒(méi)毛病。
對(duì)數(shù)階
var i = 1
let n = 100
while i < n {
i *= 2
//以下執(zhí)行復(fù)雜度為 O(1) 的算法步驟
}
i 每次都在加倍接近 n，2^x = n 得 x = log2n馋袜，將最高項(xiàng)的常數(shù)項(xiàng)變成1男旗，復(fù)雜度為 O(logn)。
平方階
var n = 100
for i in 0...n{
for j in 0...n {
//執(zhí)行時(shí)間復(fù)雜度為 O（1）的算法
}
}
這段是最簡(jiǎn)單的復(fù)雜度為 O（n2）代碼欣鳖，在計(jì)算多重循環(huán)的算法的復(fù)雜度的時(shí)候其實(shí)就是高中數(shù)列的一些相關(guān)運(yùn)算察皇，關(guān)注算法怎么越來(lái)越接近算法結(jié)束之后的執(zhí)行次數(shù)。
如：
var n = 100
for i in 0...n{
for j in i...n {
//執(zhí)行時(shí)間復(fù)雜度為 O（1）的算法
}
}
這個(gè)算法的執(zhí)行次數(shù)為 n2/2 + n/2,看起來(lái)很長(zhǎng)泽台，其實(shí)經(jīng)過(guò)計(jì)算法則處理之后這段代碼的復(fù)雜度為 O(n2)什荣。
