C語(yǔ)言?超詳細(xì)講解算法的時(shí)間復(fù)雜度和空間復(fù)雜度
1.前言
1.1 什么是數(shù)據(jù)結(jié)構(gòu)?
數(shù)據(jù)結(jié)構(gòu)(Data Structure)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式,指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
1.2 什么是算法?
算法(Algorithm):就是定義良好的計(jì)算過程,他取一個(gè)或一組的值為輸入,并產(chǎn)生出一個(gè)或一組值作為輸出。簡(jiǎn)單來說算法就是一系列的計(jì)算步驟,用來將輸入數(shù)據(jù)轉(zhuǎn)化成輸出結(jié)果。
2.算法效率
2.1 如何衡量一個(gè)算法的好壞
如何衡量一個(gè)算法的好壞呢?比如對(duì)于以下斐波那契數(shù)列:
long long Fib(int N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
斐波那契數(shù)列的遞歸實(shí)現(xiàn)方式非常簡(jiǎn)潔,但簡(jiǎn)潔一定好嗎?那該如何衡量其好與壞呢?
2.2 算法的復(fù)雜度
算法在編寫成可執(zhí)行程序后,運(yùn)行時(shí)需要耗費(fèi)時(shí)間資源和空間(內(nèi)存)資源 。因此衡量一個(gè)算法的好壞,一般是從時(shí)間和空間兩個(gè)維度來衡量的,即時(shí)間復(fù)雜度和空間復(fù)雜度。
時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢,而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。在計(jì)算機(jī)發(fā)展的早期,計(jì)算機(jī)的存儲(chǔ)容量很小。所以對(duì)空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展,計(jì) 算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度
2.3 復(fù)雜度在校招中的考察
3.時(shí)間復(fù)雜度
3.1 時(shí)間復(fù)雜度的概念
時(shí)間復(fù)雜度的定義:在計(jì)算機(jī)科學(xué)中,算法的時(shí)間復(fù)雜度是一個(gè)函數(shù),它定量描述了該算法的運(yùn)行時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間,從理論上說,是不能算出來的,只有你把你的程序放在機(jī)器上跑起來,才能知道。但是我們需要每個(gè)算法都上機(jī)測(cè)試嗎?是可以都上機(jī)測(cè)試,但是這很麻煩,所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。
一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例,算法中的基本操作的執(zhí)行次數(shù),為算法的時(shí)間復(fù)雜度即:找到某條基本語(yǔ)句與問題規(guī)模N之間的數(shù)學(xué)表達(dá)式,就是算出了該算法的時(shí)間復(fù)雜度
// 請(qǐng)計(jì)算一下Func1中++count語(yǔ)句總共執(zhí)行了多少次? void Func1(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; } printf("%d\n", count); }
Func1 執(zhí)行的基本操作次數(shù) :F(N) = N^2+2*N+10
(‘^’在此章節(jié)表示為數(shù)乘)
- N = 10 F(N) = 130
- N = 100 F(N) = 10210
- N = 1000 F(N) = 1002010
實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí),我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù),而只需要大概執(zhí)行次數(shù),那么這里我們使用大O的漸進(jìn)表示法。
3.2 大O的漸進(jìn)表示法
大O符號(hào)(Big O notation):是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。
推導(dǎo)大O階方法:
1、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2、在修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng)。
3、如果最高階項(xiàng)存在且不是1,則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。使用大O的漸進(jìn)表示法以后,F(xiàn)unc1的時(shí)間復(fù)雜度為:O(N^2)
- N = 10 F(N) = 100
- N = 100 F(N) = 10000
- N = 1000 F(N) = 1000000
通過上面我們會(huì)發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對(duì)結(jié)果影響不大的項(xiàng),簡(jiǎn)潔明了的表示出了執(zhí)行次數(shù)。
另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況:
最壞情況:任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
平均情況:任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況:任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)
例如:在一個(gè)長(zhǎng)度為N數(shù)組中搜索一個(gè)數(shù)據(jù)x
最好情況:1次找到
最壞情況:N次找到
平均情況:N/2次找到
在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況,所以數(shù)組中搜索數(shù)據(jù)時(shí)間復(fù)雜度為O(N)
3.3 常見時(shí)間復(fù)雜度計(jì)算舉例
實(shí)例1
// 計(jì)算Func2的時(shí)間復(fù)雜度? void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
實(shí)例 2
// 計(jì)算Func3的時(shí)間復(fù)雜度? void Func3(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); }
實(shí)例 3
// 計(jì)算Func4的時(shí)間復(fù)雜度? void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }
實(shí)例 4
// 計(jì)算strchr的時(shí)間復(fù)雜度? const char * strchr ( const char * str, int character );
實(shí)例 5
// 計(jì)算BubbleSort的時(shí)間復(fù)雜度? 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; } }
實(shí)例 6
// 計(jì)算BinarySearch的時(shí)間復(fù)雜度? 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);//防溢出 if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1; }
實(shí)例 7
// 計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度? long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }
實(shí)例 8
// 計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度? long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
實(shí)例答案及分析:
實(shí)例1基本操作執(zhí)行了2N+10次,通過推導(dǎo)大O階方法知道,時(shí)間復(fù)雜度為 O(N)
實(shí)例2基本操作執(zhí)行了M+N次,有兩個(gè)未知數(shù)M和N,時(shí)間復(fù)雜度為 O(N+M)
實(shí)例3基本操作執(zhí)行了10次,通過推導(dǎo)大O階方法,時(shí)間復(fù)雜度為 O(1)
實(shí)例4基本操作執(zhí)行最好1次,最壞N次,時(shí)間復(fù)雜度一般看最壞,時(shí)間復(fù)雜度為 O(N)
實(shí)例5基本操作執(zhí)行最好N次,最壞執(zhí)行了(N*(N+1)/2)次(N-1 + N-2 + N-3…+2+1),通過推導(dǎo)大O階方法+時(shí)間復(fù)雜度一般看最壞,時(shí)間復(fù)雜度為 O(N^2)。
實(shí)例6基本操作執(zhí)行最好1次(第一次就找到了),最壞O(logN)次(全找了一遍但沒找到的情況),時(shí)間復(fù)雜度為 O(logN) ps:logN在算法分析中表示是底數(shù)為2,對(duì)數(shù)為N。有些地方會(huì)寫成lgN。(建議通過折紙查找的方式講解logN是怎么計(jì)算出來的)(假設(shè)找了x次才找完,則共有2^x個(gè)數(shù)據(jù)。反過來講就是N個(gè)數(shù)據(jù)最多要找logN(底數(shù)為2)次)
實(shí)例7通過計(jì)算分析發(fā)現(xiàn)基本操作遞歸了N次,時(shí)間復(fù)雜度為O(N)。
實(shí)例8通過計(jì)算分析發(fā)現(xiàn)基本操作遞歸了2^N 次,時(shí)間復(fù)雜度為O(2N)。(1+2+4+8……+2(n-1) 再減一些次數(shù)(忽略不計(jì)))(建議畫圖遞歸棧幀的二叉樹)
總結(jié):我們想要分析算法的時(shí)間復(fù)雜度,一定要去看思想,,不能只去看程序是幾層循環(huán)。 遞歸算法時(shí)間復(fù)雜度的計(jì)算:
1.每次函數(shù)調(diào)用是O(1),那么就看遞歸次數(shù)
2.每次函數(shù)調(diào)用不是O(1),就把每次的調(diào)用次數(shù)相加。
4.空間復(fù)雜度
空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式,是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度 。
空間復(fù)雜度不是程序占用了多少bytes的空間,因?yàn)檫@個(gè)也沒太大意義,所以空間復(fù)雜度算的是變量的個(gè)數(shù)??臻g復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似,也使用大O漸進(jìn)表示法。
注意:函數(shù)運(yùn)行時(shí)所需要的??臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了,因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來確定。
實(shí)例 1
// 計(jì)算BubbleSort的空間復(fù)雜度? 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; } }
實(shí)例 2
// 計(jì)算Fibonacci的空間復(fù)雜度? // 返回斐波那契數(shù)列的前n項(xiàng) long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; ++i) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; }
實(shí)例 3
// 計(jì)算階乘遞歸Fac的空間復(fù)雜度? long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }
實(shí)例4
// 計(jì)算斐波那契遞歸Fib的空間復(fù)雜度? long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
實(shí)例答案及分析:
實(shí)例1使用了常數(shù)個(gè)額外空間,所以空間復(fù)雜度為 O(1)
實(shí)例2動(dòng)態(tài)開辟了N個(gè)空間,空間復(fù)雜度為 O(N)
實(shí)例3遞歸調(diào)用了N次,開辟了N個(gè)棧幀,每個(gè)棧幀使用了常數(shù)個(gè)空間??臻g復(fù)雜度為O(N) 4.先說答案空間復(fù)雜度為O(N) ,這是因?yàn)樗c棧幀的開辟與銷毀有關(guān)。棧幀銷毀后再開辟還是用的同一塊空間,它遞歸2^N次,開辟N個(gè)空間算出數(shù)值后銷毀空間,然后再開辟,總共用了N塊空間
總結(jié): 時(shí)間一去不復(fù)返,是累積的 空間回收以后可以重復(fù)利用
5. 常見復(fù)雜度對(duì)比
一般算法常見的復(fù)雜度如下:
總結(jié):這是數(shù)據(jù)結(jié)構(gòu)(用c語(yǔ)言實(shí)現(xiàn))的第一節(jié)課,內(nèi)容還算簡(jiǎn)單,可以抓緊時(shí)間復(fù)習(xí)c教程中的指針和結(jié)構(gòu)體等知識(shí),之后的學(xué)習(xí)會(huì)更靈活的運(yùn)用這些知識(shí)。大家加油!
到此這篇關(guān)于C語(yǔ)言 超詳細(xì)講解算法的時(shí)間復(fù)雜度和空間復(fù)雜度的文章就介紹到這了,更多相關(guān)C語(yǔ)言 時(shí)間復(fù)雜度內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
c語(yǔ)言輕松實(shí)現(xiàn)猜數(shù)字小游戲
猜數(shù)字是興起于英國(guó)的益智類小游戲,起源于20世紀(jì)中期,一般由兩個(gè)人或多人玩,也可以由一個(gè)人和電腦玩。游戲規(guī)則為一方出數(shù)字,一方猜,今天我們來用C實(shí)現(xiàn)這個(gè)游戲案例2022-04-04關(guān)于C++中構(gòu)造函數(shù)初始化成員列表的總結(jié)
下面小編就為大家?guī)硪黄P(guān)于C++中構(gòu)造函數(shù)初始化成員列表的總結(jié)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12C/C++?Qt?數(shù)據(jù)庫(kù)與ComBox實(shí)現(xiàn)多級(jí)聯(lián)動(dòng)示例代碼
Qt中的SQL數(shù)據(jù)庫(kù)組件可以與ComBox組件形成多級(jí)聯(lián)動(dòng)效果,在日常開發(fā)中多級(jí)聯(lián)動(dòng)效果應(yīng)用非常廣泛,今天給大家分享二級(jí)ComBox菜單如何與數(shù)據(jù)庫(kù)形成聯(lián)動(dòng),本文通過實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧2021-12-12深入解析Radix Sort基數(shù)排序算法思想及C語(yǔ)言實(shí)現(xiàn)示例
基數(shù)排序和桶排序、計(jì)數(shù)排序共同是三種最常用的線性排序算法,這里我們就來深入解析Radix Sort基數(shù)排序算法思想及C語(yǔ)言實(shí)現(xiàn)示例,需要的朋友可以參考下2016-07-07C++中默認(rèn)無(wú)參構(gòu)造函數(shù)的工作機(jī)制淺析
構(gòu)造函數(shù)主要作用在于創(chuàng)建對(duì)象時(shí)為對(duì)象的成員屬性賦值,構(gòu)造函數(shù)由編譯器自動(dòng)調(diào)用,無(wú)須手動(dòng)調(diào)用;析構(gòu)函數(shù)主要作用在于對(duì)象銷毀前系統(tǒng)自動(dòng)調(diào)用,執(zhí)行一些清理工作2023-02-02