算法在編寫成可執行程序的時候,main函數使用這個算法,需要調用一定的空間,消耗一定的時間。算法的效率就是通過空間和時間這兩個維度來評判的
時間複雜度:衡量一個算法的運行速度
空間複雜度:衡量一個算法運行需要開辟的額外空間
那麼我們今天先來看看時間複雜度!
時間複雜度
算法的時間複雜度是一個函數,它定量描述了該算法的運行時間。算法中基本操作的執行次數,為算法的時間複雜度
時間複雜度是一個近似值,并不是實際運行的時間
實際上代碼的運行時間,和機器的内存、cpu性能和平台都有關系,同一個代碼在不同的機器上運行時間都不一樣,如果隻以純粹的時間來考核,很難分析
找到某條基本語句與問題規模N之間的數學表達式,就算出了該算法的時間複雜度
void Test(int N)
{
int count =0;
for(int i=0;i<N;i )
{
for(int j=0;j<N;j )
{
count ;
}
}
for (int k = 0; k < 2 * N ; k)
{
count ;
}
int M = 10;
while (M--)
{
count ;
}
return;
}
請問這個代碼中,count語句執行了幾次?
F ( N ) = N 2 2 ∗ N 10 F(N)=N^2 2*N 10 F(N)=N2 2∗N 10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
你可能會簡單地認為,F(N)的結果就是我們的時間複雜度。其實并不然,我們并不需要一個精确的運行次數,隻需要知道程序運行次數的量級就行了
這裡我們使用大O漸進表示法來表示時間複雜度(空間複雜度同理)
2.1大O的漸進表示法大O符号(Big O notation):是用于描述函數漸進行為的數學符号
推導大O階方法:
(1)用常數1取代運行時間中的所有加法常數。
(2)在修改後的運行次數函數中,隻保留最高階項。
(3)如果最高階項存在且不是1,則去除與這個項目相乘的常數。得到的結果就是大O階
使用這種方法後,test1函數的時間複雜度為
O ( N 2 ) O(N^2) O(N2)
對于test1函數,在計算的時候,我們省略了最後的 10,保留了最高階數N2,即得出了它的時間複雜度
如果最高階數前面有系數,如2N,系數也将被省略
因為當N的數值很大的時候,後面的那些值對我們總運行次數的影響已經非常小了。大O的漸進表示法去掉了那些對結果影響不大的項,簡潔明了的表示出了執行次數
2.2多種情況取最壞一些算法的時間複雜度會有最好、最壞和平均的情況
最好情況:任意輸入規模的最小運行次數(下界)
平均情況:期望的運行次數
最壞情況:任意輸入規模的最大運行次數(上界)
舉個例子,當我們編寫一個在數組中查找數值的算法時,它可能會出現這幾種情況:
最好情況:1次就找到
平均情況:N/2次
最壞情況:N次
在實際中的一般情況,我們關注的是算法的最壞運行情況,所以數組中搜索數據時間複雜度為O(N)
2.3常見時間複雜度的計算NO.1
void Func1(int N) { int count = 0; for (int k = 0; k < 2 * N ; k) { count; } int M = 10; while (M--) { count; } printf("%d\n", count); }
這裡出現了兩個循環,分别是2N次和10次。前面提到了大O漸進法隻保留最高階數并省略系數,所以它的時間複雜度是O(N)
NO.2
void Func2(int N, int M) { int count = 0; for (int k = 0; k < M; k) { count; } for (int k = 0; k < N ; k) { count; } printf("%d\n", count); }
這裡出現了次數為N和M的兩層循環:
當M和N差不多大的時候,時間複雜度可以理解為O(M)或O(N)
當M遠遠大于N時,時間複雜度為O(M)
一般情況取O(M N)
NO.3 常數階
void Func3(int N) { int count = 0; for (int k = 0; k < 100; k) { count; } printf("%d\n", count); }
這裡我們得知了具體的循環次數為100,是一常數,時間複雜度為O(1),代表常數階
隻要循環次數已知,為一常數且和所傳參數無關,其時間複雜度即為O(1)
NO.4 strchr
//計算strchr的時間複雜度 const char * strchr ( const char * str, int character );
看到這道題的時候,你可能會一愣,strchr是什麼?
可這裡面沒有strchr,但有strstr
strstr函數的作用:在字符串1中尋找是否有字符串2
其中第二個str代表的是string字符串,那我們是不是可以猜想,chr代表的是char字符,其作用是在一個字符串中查找是否有一個字符呢?
當然,光是猜想肯定是不夠的,我們還需要求證一下
打開 cplusplus網站,搜索strchr,即可轉到函數定義
可以看到,該函數的作用是定位字符串中第一次出現該字符的位置,返回值是一個pointer指針
和我們猜想的一樣,它的作用就是在字符串中查找一個字符,并返回它第一次出現的位置的地址。
這樣一來,strchr函數的時間複雜度就很清楚了,就是遍曆字符串所需要的次數,O(N)
NO.5 冒泡排序
void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }
冒泡排序是一個非常經典的代碼,其思路就是遍曆整個數組,如果待排序數字大于它的下一位,則交換這兩個數字
N個數字的數組需要N-1次排序才能完成
每一次排序都需要遍曆一次數組
這樣算來,冒泡排序的循環次數就是兩個N,即為O(N2)
能否通過循環層級判斷?
細心的你可能會發現,上述代碼中出現了兩層循環,那是不是可以通過循環層級來判斷時間複雜度呢?
并不能!
for(int i=0;i<n;i ) { for(int j=0;j<3;j ) printf("hehe\n"); }
如果是上述這種兩次循環的情況,會打印3n次呵呵,其時間複雜度是O(N)而不是N2
我們要準确分析算法的思路,并不能簡單地通過循環層級來判斷時間複雜度
NO.6 二分查找
int BinarySearch(int* a, int n, int x){ assert(a); int begin = 0; int end = n-1; while (begin < end) { int mid = begin ((end-begin)>>1);//使用位移操作符來模拟/2,防止begin和end相加後超出int範圍 if (a[mid] < x) begin = mid 1; else if (a[mid] > x) end = mid; else return mid; } return -1;}
二分查找的思路這裡不再贅述
假設我們找了x次,每一次查找都會使查找範圍減半
N/2/2/2/2 ……
最後我們可以得出2條公式
2 x = N 2^x=N 2x=N
x = l o g 2 N x=log_2N x=log2N
最好情況:O(1)
最壞情況:O(logN)
通過時間複雜度的對比,我們就能看出二分查找的優勢在那裡了
可以看到,當數據很大的時候,O(logN)的算法執行次數比O(N)少了特别多!!(來自BT-7274的肯定)
NO.7 計算N!
// 計算階乘遞歸Fac的時間複雜度? long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }
對于這個階乘的遞歸函數而言,每次函數調用是O(1),時間複雜度主要看遞歸次數
對于數字N而言,遞歸需要N次,時間複雜度是O(N)
遞歸算法時間複雜度計算
如果每次函數調用是O(1),看遞歸次數
每次函數調用不是O(1),那麼就看他遞歸調用中次數的累加
NO.8 斐波那契數列
// 計算斐波那契遞歸Fib的時間複雜度? long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) Fib(N-2); }
每次遞歸,次數都會增加,總的來說是以2^x的量級增加的(x代表行數)
1 2 4 8 … … 2 X − 2 1 2 4 8 …… 2^{X-2} 1 2 4 8 …… 2X−2
這裡一共有x-1項,用等比數列的求和公式得出,結果為2x-1
所以最後得出的時間複雜度為O(2N)
需要注意的是,當遞歸調用到底部時,有一些調用會較早退出,這部分位于金字塔的右下角
由于時間複雜度隻是一個估算值,這一部分缺失的調用次數對總運行次數的影響不大,故忽略掉
NO.9
void fun(int n) { int i=l; while(i<=n) i=i*2; }
此函數有一個循環,但是循環沒有被執行n次,i每次都是2倍進行遞增,所以循環隻會被執行log2n次
NO.10
給定一個整數sum,從有N個有序元素的數組中尋找元素a,b,使得a b的結果最接近sum,最快的平均時間複雜度是?
A. O(n)//√ B. O(n^2) C. O(nlogn) D. O(logn)
數組元素有序,所以a,b兩個數可以分别從開始和結尾處開始搜,根據首尾元素的和是否大于sum,決定搜索的移動,整個數組被搜索一遍,就可以得到結果,所以最好時間複雜度為n
-----------------------------------
51CTO丨作者:慕雪年華
為了幫助大家,輕松,高效學習C語言/C ,給大家分享我收集的資源,從最零基礎開始的,幫助大家在學習C語言的道路上披荊斬棘!
編程學習書籍分享:
編程學習視頻分享:
整理分享(多年學習的源碼、項目實戰視頻、項目筆記,基礎入門教程)最重要的是你可以在群裡面交流提問編程問題哦!
對于C/C 感興趣可以關注小編在後台私信我:【編程交流】一起來學習哦!可以領取一些C/C 的項目學習視頻資料哦!已經設置好了關鍵詞自動回複,自動領取就好了!
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!