遇見的題目——關于時間復雜度
在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是：
第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個算法的時間復雜度為Ο(n+n2)=Ο(n2)。
注、加法原則：T(n)=O(f(n))+O(g(n))=O(max(fn,gn))
常見的算法時間復雜度由小到大依次為：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)<O(n^n)
Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要算法中不存在循環語句，其時間復雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者是有效算法，把這類問題稱為P類問題，而把后者稱為NP問題。
posted on 2020-03-09 17:26 666wolaichuangmen 閱讀(378) 評論(0) 收藏 舉報
浙公網安備 33010602011771號