演算法的時間複雜度

對於演算法工程師來講，時間複雜度是一個很重要的計算量。通常用大O表示法即O()來體現演算法時間複雜度

時間複雜度三定律

?用常數1取代運行時間中所有加法常數

?修改後的運行次數函數中只保留最高階項

?如果最高階項存在且不為1，則去除最高階項係數。

時間複雜度計算

常數階

上面演算法運行次數函數為f(n)=3，故該演算法時間複雜度為O(1)

線性階

上面演算法for循環中的代碼執行了n次，故該演算法時間複雜度為O(n)

對數階

由式2^x=n得上面演算法while循環中的次數x=log?n，故該演算法時間複雜度為O(logn)

平方階

內外層循環都是n次，故該演算法的時間複雜度為O(n^2)

內循環次數隨著i的變化而變化，可計算n+(n-1)+(n-2)+...+1=n2/2+n/2

提取最高階，化最高階係數為1，故該演算法的時間複雜度為O(n2)

時間複雜度排序

常用的時間複雜度消耗時間從小到大依次為：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！