算法時(shí)間復(fù)雜度

定義：在進(jìn)行算法分析時(shí)，語(yǔ)句總度執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T(n) = O(f(n))。它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱(chēng)作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度。其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)。

(執(zhí)行次數(shù) == 時(shí)間)

推導(dǎo)大O階方法

·? ? 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。

·? ? 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。

·? ? 如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

算法的空間復(fù)雜度

定義：算法的空間復(fù)雜度通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法的空間復(fù)雜度的計(jì)算公式記作：S(n) = O(f(n))，其中n為問(wèn)題的規(guī)模，f(n)為語(yǔ)句關(guān)于n所占存儲(chǔ)空間的函數(shù)。

當(dāng)直接要讓我們求"復(fù)雜度"時(shí)，通常指的是時(shí)間復(fù)雜度。