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