时间复杂度计算杂记
算法時(shí)間復(fù)雜度的計(jì)算 [整理]
時(shí)間復(fù)雜度算法?
基本的計(jì)算步驟
?
時(shí)間復(fù)雜度的定義
??? 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無(wú)窮大時(shí)，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度(O是數(shù)量級(jí)的符號(hào) )，簡(jiǎn)稱時(shí)間復(fù)雜度。
?
根據(jù)定義，可以歸納出基本的計(jì)算步驟
1. 計(jì)算出基本操作的執(zhí)行次數(shù)T(n)
??? 基本操作即算法中的每條語(yǔ)句（以;號(hào)作為分割），語(yǔ)句的執(zhí)行次數(shù)也叫做語(yǔ)句的頻度。在做算法分析時(shí)，一般默認(rèn)為考慮最壞的情況。
?
2. 計(jì)算出T(n)的數(shù)量級(jí)
??? 求T(n)的數(shù)量級(jí)，只要將T(n)進(jìn)行如下一些操作：
??? 忽略常量、低次冪和最高次冪的系數(shù)
?
??? 令f(n)=T(n)的數(shù)量級(jí)。
?
3. 用大O來(lái)表示時(shí)間復(fù)雜度
??? 當(dāng)n趨近于無(wú)窮大時(shí)，如果lim(T(n)/f(n))的值為不等于0的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n))。
?
一個(gè)示例：
(1) int num1, num2;
(2) for(int i=0; i<n; i++){
(3)???? num1 += 1;
(4)???? for(int j=1;j<=n; j*=2){
(5)????????num2 += num1;
(6)???? }
(7) }
?
分析：
1.
語(yǔ)句int num1, num2;的頻度為1；
語(yǔ)句i=0;的頻度為1；
語(yǔ)句i<n; i++; num1+=1; j=1; 的頻度為n；
語(yǔ)句j<=n; j*=2; num2+=num1;的頻度為n*log2n；
T(n) = 2 + 4n + 3n*log2n
?
2.
忽略掉T(n)中的常量、低次冪和最高次冪的系數(shù)
f(n) = n*log2n
?
3.
lim(T(n)/f(n)) = (2+4n+3n*log2n) /(n*log2n)
????????????????????= 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3
?
當(dāng)n趨向于無(wú)窮大，1/n趨向于0，1/log2n趨向于0
所以極限等于3。
?
T(n) = O(n*log2n)
?
簡(jiǎn)化的計(jì)算步驟
?
再來(lái)分析一下，可以看出，決定算法復(fù)雜度的是執(zhí)行次數(shù)最多的語(yǔ)句，這里是num2 += num1，一般也是最內(nèi)循環(huán)的語(yǔ)句。
?
并且，通常將求解極限是否為常量也省略掉？
?
于是，以上步驟可以簡(jiǎn)化為：
1. 找到執(zhí)行次數(shù)最多的語(yǔ)句
2. 計(jì)算語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)
3. 用大O來(lái)表示結(jié)果
?
繼續(xù)以上述算法為例，進(jìn)行分析：
1.
執(zhí)行次數(shù)最多的語(yǔ)句為num2 += num1
?
2.
T(n) = n*log2n
f(n) = n*log2n
?
3.
// lim(T(n)/f(n)) = 1
T(n) = O(n*log2n)
?
--------------------------------------------------------------------------------
一些補(bǔ)充說(shuō)明
最壞時(shí)間復(fù)雜度
??? 算法的時(shí)間復(fù)雜度不僅與語(yǔ)句頻度有關(guān)，還與問(wèn)題規(guī)模及輸入實(shí)例中各元素的取值有關(guān)。一般不特別說(shuō)明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)。
?
求數(shù)量級(jí)
即求對(duì)數(shù)值(log)，默認(rèn)底數(shù)為10，簡(jiǎn)單來(lái)說(shuō)就是“一個(gè)數(shù)用標(biāo)準(zhǔn)科學(xué)計(jì)數(shù)法表示后，10的指數(shù)”。例如，5000=5x10 3 (log5000=3) ，數(shù)量級(jí)為3。另外，一個(gè)未知數(shù)的數(shù)量級(jí)為其最接近的數(shù)量級(jí)，即最大可能的數(shù)量級(jí)。
?
求極限的技巧
要利用好1/n。當(dāng)n趨于無(wú)窮大時(shí)，1/n趨向于0
?
--------------------------------------------------------------------------------
一些規(guī)則(引自：時(shí)間復(fù)雜度計(jì)算 )
1) 加法規(guī)則
T(n,m) = T1(n) + T2(n) = O (max ( f(n),g(m) )
?
2) 乘法規(guī)則
T(n,m) = T1(n) * T2(m) = O (f(n) * g(m))
?
3) 一個(gè)特例（問(wèn)題規(guī)模為常量的時(shí)間復(fù)雜度）
在大O表示法里面有一個(gè)特例，如果T1(n) ＝ O(c)， c是一個(gè)與n無(wú)關(guān)的任意常數(shù)，T2(n) = O ( f(n) ) 則有
T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O(f(n) )
?
也就是說(shuō)，在大O表示法中，任何非0正常數(shù)都屬于同一數(shù)量級(jí)，記為O(1)。
?
4) 一個(gè)經(jīng)驗(yàn)規(guī)則
復(fù)雜度與時(shí)間效率的關(guān)系：
c < log2n < n < n*log2n < n2< n3 < 2n < 3n < n! （c是一個(gè)常量）
|--------------------------|--------------------------|-------------|
?????????較好????????????????????一般?????????????較差
其中c是一個(gè)常量，如果一個(gè)算法的復(fù)雜度為c 、 log2n 、n 、 n*log2n,那么這個(gè)算法時(shí)間效率比較高，如果是 2n , 3n ,n!,那么稍微大一些的n就會(huì)令這個(gè)算法不能動(dòng)了，居于中間的幾個(gè)則差強(qiáng)人意。
?
--------------------------------------------------------------------------------------------------
復(fù)雜情況的分析
?
以上都是對(duì)于單個(gè)嵌套循環(huán)的情況進(jìn)行分析，但實(shí)際上還可能有其他的情況，下面將例舉說(shuō)明。
?
1.并列循環(huán)的復(fù)雜度分析
將各個(gè)嵌套循環(huán)的時(shí)間復(fù)雜度相加。
?
例如：
?
for (i=1; i<=n; i++)
??? x++;
?
for (i=1; i<=n; i++)
??? for (j=1; j<=n; j++)
??????? x++;
?
解：
第一個(gè)for循環(huán)
T(n) = n
f(n) = n
時(shí)間復(fù)雜度為Ο(n)
?
第二個(gè)for循環(huán)
T(n) = n2
f(n) = n2
時(shí)間復(fù)雜度為Ο(n2)
?
整個(gè)算法的時(shí)間復(fù)雜度為Ο(n+n2) = Ο(n2)。
?
2.函數(shù)調(diào)用的復(fù)雜度分析
例如：
public void printsum(int count){
??? int sum = 1;
??? for(int i= 0; i<n;i++){
?????? sum +=i;
??? }? ?
??? System.out.print(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;? ?
??? System.out.print(sum);
}
這樣算法的時(shí)間復(fù)雜度將由原來(lái)的O(n)降為O(1)，大大地提高了算法的性能。
?
3.混合情況（多個(gè)方法調(diào)用與循環(huán)）的復(fù)雜度分析
例如：
public void suixiangMethod(int n){
??? printsum(n);//1.1
??? for(int i= 0; i<n;i++){
??????printsum(n); //1.2
??? }
??? for(int i= 0; i<n;i++){
??????for(int k=0; k
???????System.out.print(i,k); //1.3
????? }
? }
suixiangMethod 方法的時(shí)間復(fù)雜度需要計(jì)算方法體的各個(gè)成員的復(fù)雜度。
也就是1.1+1.2+1.3 = 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++)???? ?
??????for(j=1;j<=n;j++)
????????sum++；?????? /* 執(zhí)行次數(shù)n2 */
解：T(n) = 1 + n2 = O(n2)
?
?? for (i=1;i<n;i++)
?? {
??????y=y+1;??????? ①? ?
?????? for(j=0;j<=(2*n);j++)?? ?
?????????x++;??????? ②?????
??}??????? ?
解：? 語(yǔ)句1的頻度是n-1
????????語(yǔ)句2的頻度是(n-1)*(2n+1) = 2n2-n-1
????????T(n) = 2n2-n-1+(n-1) = 2n2-2
????????f(n) = n2
????????lim(T(n)/f(n)) = 2 + 2*(1/n2) = 2
????????T(n) = O(n2).
?
O(n)???????????????????????????????????????
?? a=0;
??b=1;????????????????????①
?? for (i=1;i<=n;i++) ②
?? { ?
????? s=a+b; ③
????? b=a; ④ ?
????? a=s; ⑤
?? }
解：? 語(yǔ)句1的頻度：2,?????? ?
????????語(yǔ)句2的頻度：n,?????? ?
????????語(yǔ)句3的頻度：n,?????? ?
????????語(yǔ)句4的頻度：n,?? ?
????????語(yǔ)句5的頻度：n,?????????????????????????????????
????????T(n) = 2+4n
????????f(n) = n
????????lim(T(n)/f(n)) = 2*(1/n) + 4 = 4
????????T(n) = O(n).??? ?
???????????????????????????????????????????????????????????????????????????
O(log2n)
??i=1;?????? ①
?? while (i<=n)
????? i=i*2; ②
解：語(yǔ)句1的頻度是1,?
?????? 設(shè)語(yǔ)句2的頻度是t,? 則：nt<=n;?t<=log2n
?????? 考慮最壞情況，取最大值t=log2n,
???????T(n) = 1 + log2n
???????f(n) = log2n
???????lim(T(n)/f(n)) = 1/log2n + 1 = 1
???????T(n) = O(log2n)
?
?O(n3)
?? for(i=0;i<n;i++)
?? {?
?????for(j=0;j<i;j++)?
????? {
????????for(k=0;k<j;k++)
???????????x=x+2;?
????? }
?? }
解：當(dāng)i=m, j=k的時(shí)候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí), j 可以取 0,1,...,m-1 ,? 所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環(huán)共進(jìn)行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/2次
T(n) = n(n+1)(n-1)/2 = (n3-n)/2
f(n) = n3
所以時(shí)間復(fù)雜度為O(n3)。
?
總結(jié)
- 上一篇： 用python做股票因子分析_关于SPS
- 下一篇： 黑马程序员—黑客与画家——工作3年再转型