算法時間復(fù)雜度的計算(編輯修改稿)
2024-08-22 09:45 本頁面
【文章內(nèi)容簡介】 n時間復(fù)雜度為Ο(n)第二個for循環(huán)T(n) = n2f(n) = n2時間復(fù)雜度為Ο(n2)整個算法的時間復(fù)雜度為Ο(n+n2) = Ο(n2)。 例如：public void printsum(int count){ int sum = 1。 for(int i= 0。 in。 i++){ sum += i。 } (sum)。}分析：記住，只有可運(yùn)行的語句才會增加時間復(fù)雜度，因此，上面方法里的內(nèi)容除了循環(huán)之外，其余的可運(yùn)行語句的復(fù)雜度都是O(1)。所以printsum的時間復(fù)雜度 = for的O(n)+O(1) = 忽略常量 = O(n)*這里其實可以運(yùn)用公式 num = n*(n+1)/2，對算法進(jìn)行優(yōu)化，改為：public void printsum(int count){ int sum = 1。 sum = count * (count+1)/2。 (sum)。}這樣算法的時間復(fù)雜度將由原來的O(n)降為O(1)，大大地提高了算法的性能。 （多個方法調(diào)用與循環(huán)）的復(fù)雜度分析 例如：public void suixiangMethod(int n){ printsum(n)。// for(int i= 0。 in。 i++){ printsum(n)。 // } for(int i= 0。 in。 i++){ for(int k=0。 k (i,k)。 // } }suixiangMethod 方法的時間復(fù)雜度需要計算方法體的各個成員的復(fù)雜度。++ = O(1)+O(n)+O(n2) 忽略常數(shù) 和 非主要項 == O(n2)更多的例子 O(1) 交換i和j的內(nèi)容temp=i。i=j。j=temp。 以上三條單個語句的頻度為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的時間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是O(1)。O(n2) sum=0； /* 執(zhí)行次數(shù)1 */ for(i=1。i=n。i
物理相關(guān)推薦
鄂ICP備17016276號-1