目錄
- 1、大O表示法
- 2、時間復雜度分析
- 2.1 只關注執行次數最多的一段代碼
- 2.2 加法法則，總復雜度等于量級最大的代碼的復雜度
- 2.3 乘法法則，嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積
- 3、常見時間復雜度示例
- 3.1 O(1)
- 3.2 O(logn)
- 4、復雜度量級
- 4.1 多現實量級
- 4.2 非多項式量級（NP)
1、大O表示法
大O表示法并不是具體代碼執行的時間，而是標識代碼執行時間隨資料規模增長的變化趨勢，當資料規模很大的時候，只需要記錄最大量級就可以了，比如實際復雜度為:
\[T(n)=n^2 + 2n +3 \]最終用大O表示法為：
\[T(n)=O(n^2) \]因為當n非常大的時候2n和3的大小是可以忽略的
2、時間復雜度分析
2.1 只關注執行次數最多的一段代碼
示例代碼：
public int sum(int n)
{
int sum=0;
for(i=0; i< j; i++)
{
sum=sum + i;
}
return sum;
}
以上代碼只需要關注那個for回圈即可(執行n次)，其他賦值等操作為常數級復雜度，與n的數量級沒有關系，所以上面代碼的復雜度為：O(n)
2.2 加法法則，總復雜度等于量級最大的代碼的復雜度
示例代碼：
public int sum(int n)
{
int sum=0;
for(i=0; i< n; i++)
{
sum=sum + i;
}
int sum2=0;
for(i=0; i< n; i++)
{
for(j=0;j<n;j++)
{
sum = sum + i *j
}
}
return sum + sum2;
}
以上復雜度為O(n) + O(n2)，基于上面的分析，取最大量級，得知最終的復雜度為O(n2)，
2.3 乘法法則，嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積
示例代碼：
public int calculate(int n)
{
int sum=0;
for(i=0; i< n; i++)
{
sum=sum + fun(i);
}
}
public int fun(int n)
{
int sum=0;
for(i=0; i< n; i++)
{
sum=sum + i;
}
return sum;
}
以上復雜度為O(n) * O(n)，為O(n^2)，
3、常見時間復雜度示例
3.1 O(1)
O(1)表示常數級執行次數，并不是表示只執行一次，
public int calculate()
{
int i=1;
int j=2;
return i+j
}
以上代碼執行了3次，是個常數級別，其復雜度是O(1)，而不是O(3)，
3.2 O(logn)
代碼：
public void fun(int n)
{
int i=0;
while(i < n)
{
i= i*2;
}
}
上述回圈的執行次數所多少呢，
\[2^k=n \]k即為回圈的執行次數：
\[k=logn \]所以復雜度為O(logn)，
4、復雜度量級
4.1 多現實量級
- 常亮階O(1)
- 對數階O(logn)
- 線性階O(n)
- 線性對數階O(nlogn)
- 平方階O(n2），，，k次方階O(nk）
4.2 非多項式量級（NP)
- 指數階O(2^n)
- 階乘階O(n!)
當N越來越大時，非多項式級演算法的執行時間會急劇增加，效率非常低下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282820.html
標籤：其他