定義
在進行算法分析時,語句總的執行次數T(n)時關于問題規模n的函數,進而分析T(n)随n的變化情況并确定T(n)的數量級。算法的時間複雜度,也就是算法的時間度量,記作:T(n) = O(f(n))。它表示歲問題規模n的增大,稱作算法的漸進時間複雜度,簡稱為時間複雜度。其中f(n)時問題規模n的某個函數。
說了半天就差不多要知道這個東西
執行此時==時間
O()
來提現算法時間複雜度的記法,稱為大O記法
一般情況下,随着輸入規模n的增大,T(n)增長最
慢
的算法為最優算法
推導大O階方法
- 用常數1取代運作時間中的所有加法常數
- 在修改後的運作次數函數中,隻保留最高階項
- 如果最高階項數存在而且不是1,則去除與這個項相乘的常數
- 得到的最後結果就是大O階
常數階:O(1)
線性階:O(n)
一般含有非嵌套循環涉及線性階,對應計算次數呈直線增長
int n = 100, sum = 0;
for(int i = 0; i < n; i++)
{
sum += i;
}
平方階:O(n^2)
如果n=100,外層執行一次,内層執行100次,是以程式執行了100^2次
int i, j, n = 100;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf("hello");
}
}
但是如果存在
int i, j, n = 100;
for (i = 0; i < n; i++)
{
for (j = i; j < n; j++)
{
printf("hello");
}
}
他還是O(n^2)