C語言數(shù)據結構基石之時間與空間復雜度詳解
一、復雜度的概念
- 一個算法的好壞，主要是對比兩者的時間和空間兩個維度，也就是時間和空間復雜度。
- 時間復雜度主要衡量一個算法運行的快慢，空間復雜度主要衡量一個算法運行需要的額外空間
二、時間復雜度
- 算法的時間復雜度是一個函數(shù)式T(N)，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。
- 注：編譯器的不同，編譯所需要的時間也不同。越新的編譯器，編譯的時間往往比舊的編譯器快
- 當一個算法函數(shù)式為
T(N) = N,和另一個算法函數(shù)式為T(N) = N^2比較，必然是第一個快
1、大O的漸進表示法
大的漸進表示法的規(guī)則：
- 時間復雜度函數(shù)式T(N)中，只保留最高階項，去掉那些低階項(當N無窮大時，低階項的影響越來越小)
- 如果最高階項是一個一次線性函數(shù)，則去除常數(shù)系數(shù)(當N無窮大時，1的影響很小)
- T(N)中如果沒有N相關的項目，只有常數(shù)項，用常數(shù)1取代所有加法常數(shù)
我們來判斷一段代碼的時間復雜度
// 請計算?下Func1中++count語句總共執(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;
}
}Func1 執(zhí)?的基本操作次數(shù)：T (N) = N2 + 2 ∗ N + 10
通過對N取值分析，對結果影響最大的?項是N2
通過以上方法，可以大致評估Func1的時間復雜度為：O(N2 )
2、函數(shù)clock計算運算時間
我們想計算代碼運算的時間，可以運用clock函數(shù)進行計算。運算過程為運算末-運算初
#include<stdio.h>
#include<time>
int main()
{
int i = 0;
int begin = clock();
int x = 10;
for(i = 0; i < n; i++)
{
x++;
}
int end = clock();
//計算運行時間
printf("%dms", end - begin);
return 0;
}3、常見復雜度對比
| 5201314 | 0(1) | 常數(shù)階 |
|---|---|---|
| 3n+4 | O(n) | 線性階 |
| 3n^2+4n+5 | 0(n^2) | 平方階 |
| 310g(2)n+4 | 0(1ogn) | 對數(shù)階 |
| 2n+3nlog(2)n+14 | O(nlogn) | nlogn階 |
| n3+2n2+4n+6 | 0(n^3) | 立方階 |
| 2^n | 0(2^n) | 指數(shù)階 |
3.1常數(shù)項復雜度
#include<stdio.h>
int main()
{
int x = 0;
scnaf("%d", &x);
printf("%d", x);
return 0;
}執(zhí)行的基本操作次數(shù)：T (N) = 3
根據推導規(guī)則第3條得出時間復雜度為：O(1)
3.2線性時間復雜度
案例1
// 計算Func2的時間復雜度？
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);
}Func2執(zhí)行的基本操作次數(shù)：T (N) = 2N + 10
根據推導規(guī)則第3條得出Func2的時間復雜度為：O(N)
案例2
// 計算Func3的時間復雜度？
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);
}Func3執(zhí)行的基本操作次數(shù)：T (N) = M + N
因此：Func3的時間復雜度為：O(N)
3.3平方階復雜度
#include<stdio.h>
int main()
{
int x = 0;
int begin = clock();
int n = 100000;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
x++;
}
}
int end = clock();
printf("%d\n", x);
printf("%dms\n", end - begin);
return 0;
}執(zhí)行的基本操作次數(shù)：T (N) = i * j
因此：時間復雜度為：O(N^2)
3.4對數(shù)復雜度
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
當n=2時，執(zhí)行次數(shù)為1
當n=4時，執(zhí)行次數(shù)為2
當n=16時，執(zhí)行次數(shù)為4
假設執(zhí)行次數(shù)為x ，則2x=n
因此執(zhí)行次數(shù)：x=log n
因此：func5的時間復雜度取最差情況為：O(log2 n)
3.5遞歸函數(shù)
單遞歸
遞歸時間復雜度：所有遞歸調用次數(shù)的累加
// 計算階乘遞歸Fac的時間復雜度？
long long Fac(size_t N)
{
if(0 == N)
return Fac(N-1)*N;
}
調??次Fac函數(shù)的時間復雜度為 O(1)，而在Fac函數(shù)中，存在n次遞歸調用Fac函數(shù)
因此：return 1;
階乘遞歸的時間復雜度為：O(n)
我們再來看一下往遞歸里加個for循環(huán)：此時遞歸的時間復雜度為：O(n^2)
雙遞歸
三、空間復雜度
空間復雜度算的是變量個數(shù)，是對一個算法在運行過程中臨時占用存儲空間大小的量度，同樣也使用大O漸進表示法。(一般在編程中不考慮空間復雜度，而多用時間復雜度?？臻g復雜度多運用在嵌入式)
注意：函數(shù)運行時所需要的棧空間(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定
我們先來看一下經典的冒泡排序
冒泡排序O(1)
// 計算BubbleSort的時間復雜度？
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ù)棧幀在編譯期間已經確定好了，只需要關注函數(shù)在運行時額外申請的空間。
BubbleSort額外申請的空間有exchange等有限個局部變量，使用了常數(shù)個額外空間，因此空間復雜度為 O(1)
三個反置O(N)
void reverse(int* nums, int left, int right)
{
while (left < right)
{
int tap = nums[left];
nums[left] = nums[right];
nums[right] = tap;
left++;
right--;
}
}
int main()
{
int nums[] = { 1,2,3,4,5,6,7 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int k = 0;
scanf("%d", &k);
k %= numsSize;
reverse(nums, 0, numsSize - k - 1);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize - 1);
for (int i = 0; i < numsSize; i++)
{
printf("%d ", nums[i]);
}
return 0;
}由于創(chuàng)建了個數(shù)組，數(shù)組的空間復雜度為O(N)
空間復雜度一般只會出現(xiàn)O(1),O(N),O(N^2)，在復雜度中，還是更看重時間復雜度
以上就是C語言數(shù)據結構基石之時間與空間復雜度詳解的詳細內容，更多關于C語言時間復雜度與空間復雜度的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了C++知識點之成員函數(shù)中const的用法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要為大家詳細介紹了Qt中QList與QLinkedList類的常用方法，文中的示例代碼講解詳細，對我們學習Qt有一定的幫助，需要的可以參考一下2022-12-12
本文主要介紹了C++11中互斥鎖的使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-06-06
Visual Studio中scanf函數(shù)報錯的幾種解決方法
本文主要介紹了Visual Studio中scanf函數(shù)報錯的幾種解決方法,文中通過圖文示例介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2025-03-03
VC下通過系統(tǒng)快照實現(xiàn)進程管理的方法
這篇文章主要介紹了VC下通過系統(tǒng)快照實現(xiàn)進程管理的方法,較為詳細的講述了VC下通過系統(tǒng)快照實現(xiàn)進程管理的原理與具體實現(xiàn)方法,非常具有實用價值,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C++堆排序算法,簡單分析了堆排序算法的原理并結合實例形式分析了C++實現(xiàn)堆排序的具體操作技巧,需要的朋友可以參考下2017-08-08
《2048》是比較流行的一款數(shù)字游戲。原版2048首先在github上發(fā)布，原作者是Gabriele Cirulli。它是基于《1024》和《小3傳奇》的玩法開發(fā)而成的新型數(shù)字游戲。2014-06-06
這篇文章主要給大家介紹了關于c++11中regex正則表達式的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用c++11具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-11-11
本文主要介紹了c++11中std::move函數(shù)的使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
C 語言getchar()函數(shù)用法、原理與避坑指南(實用示例)
這篇文章給大家介紹了C 語言 getchar()函數(shù)用法、原理,文章提供了示例代碼,幫助理解緩沖區(qū)的工作原理,并給出了實用的避坑指南,感興趣的朋友跟隨小編一起看看吧2026-01-01