一、復(fù)雜度的概念

• 一個(gè)算法的好壞，主要是對(duì)比兩者的時(shí)間和空間兩個(gè)維度，也就是時(shí)間和空間復(fù)雜度。
• 時(shí)間復(fù)雜度主要衡量一個(gè)算法運(yùn)行的快慢，空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行需要的額外空間

二、時(shí)間復(fù)雜度

• 算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)式T(N)，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。
• 注：編譯器的不同，編譯所需要的時(shí)間也不同。越新的編譯器，編譯的時(shí)間往往比舊的編譯器快
• 當(dāng)一個(gè)算法函數(shù)式為T(N) = N,和另一個(gè)算法函數(shù)式為 T(N) = N^2比較，必然是第一個(gè)快

1、大O的漸進(jìn)表示法

大的漸進(jìn)表示法的規(guī)則：

1. 時(shí)間復(fù)雜度函數(shù)式T(N)中，只保留最高階項(xiàng)，去掉那些低階項(xiàng)(當(dāng)N無(wú)窮大時(shí)，低階項(xiàng)的影響越來(lái)越小)
2. 如果最高階項(xiàng)是一個(gè)一次線性函數(shù)，則去除常數(shù)系數(shù)(當(dāng)N無(wú)窮大時(shí)，1的影響很小)
3. T(N)中如果沒(méi)有N相關(guān)的項(xiàng)目，只有常數(shù)項(xiàng)，用常數(shù)1取代所有加法常數(shù)

我們來(lái)判斷一段代碼的時(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;
	}
}

Func1 執(zhí)?的基本操作次數(shù)：T (N) = N2 + 2 ∗ N + 10
通過(guò)對(duì)N取值分析，對(duì)結(jié)果影響最大的?項(xiàng)是N2
通過(guò)以上方法，可以大致評(píng)估Func1的時(shí)間復(fù)雜度為：O(N2 )

2、函數(shù)clock計(jì)算運(yùn)算時(shí)間

我們想計(jì)算代碼運(yùn)算的時(shí)間，可以運(yùn)用clock函數(shù)進(jìn)行計(jì)算。運(yùn)算過(guò)程為運(yùn)算末-運(yùn)算初

#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();
	//計(jì)算運(yùn)行時(shí)間
	printf("%dms", end - begin);
	return 0;
}

3、常見(jiàn)復(fù)雜度對(duì)比

3.1常數(shù)項(xiàng)復(fù)雜度

#include<stdio.h>
int main()
{
	int x = 0;
	scnaf("%d", &x);
	printf("%d", x);
	return 0;
}

執(zhí)行的基本操作次數(shù)：T (N) = 3
根據(jù)推導(dǎo)規(guī)則第3條得出時(shí)間復(fù)雜度為：O(1)

3.2線性時(shí)間復(fù)雜度

案例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);
}

Func2執(zhí)行的基本操作次數(shù)：T (N) = 2N + 10
根據(jù)推導(dǎo)規(guī)則第3條得出Func2的時(shí)間復(fù)雜度為：O(N)

案例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);
}

Func3執(zhí)行的基本操作次數(shù)：T (N) = M + N
因此：Func3的時(shí)間復(fù)雜度為：O(N)

3.3平方階復(fù)雜度

#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
因此：時(shí)間復(fù)雜度為：O(N^2)

3.4對(duì)數(shù)復(fù)雜度

void func5(int n)
{
	int cnt = 1;
	while (cnt < n)
	{
		cnt *= 2;
	}
}

當(dāng)n=2時(shí)，執(zhí)行次數(shù)為1
當(dāng)n=4時(shí)，執(zhí)行次數(shù)為2
當(dāng)n=16時(shí)，執(zhí)行次數(shù)為4
假設(shè)執(zhí)行次數(shù)為x ，則2x=n
因此執(zhí)行次數(shù)：x=log n
因此：func5的時(shí)間復(fù)雜度取最差情況為：O(log2 n)

3.5遞歸函數(shù)

單遞歸

遞歸時(shí)間復(fù)雜度：所有遞歸調(diào)用次數(shù)的累加

// 計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度？

long long Fac(size_t N)
{
	if(0 == N)
	return Fac(N-1)*N;
}

調(diào)??次Fac函數(shù)的時(shí)間復(fù)雜度為 O(1)，而在Fac函數(shù)中，存在n次遞歸調(diào)用Fac函數(shù)
因此：return 1;
階乘遞歸的時(shí)間復(fù)雜度為：O(n)

我們?cè)賮?lái)看一下往遞歸里加個(gè)for循環(huán)：此時(shí)遞歸的時(shí)間復(fù)雜度為：O(n^2)

雙遞歸

三、空間復(fù)雜度

空間復(fù)雜度算的是變量個(gè)數(shù)，是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，同樣也使用大O漸進(jìn)表示法。(一般在編程中不考慮空間復(fù)雜度，而多用時(shí)間復(fù)雜度?？臻g復(fù)雜度多運(yùn)用在嵌入式)

注意：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過(guò)函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來(lái)確定
我們先來(lái)看一下經(jīng)典的冒泡排序

冒泡排序O(1)

// 計(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ù)棧幀在編譯期間已經(jīng)確定好了，只需要關(guān)注函數(shù)在運(yùn)行時(shí)額外申請(qǐng)的空間。
BubbleSort額外申請(qǐng)的空間有exchange等有限個(gè)局部變量，使用了常數(shù)個(gè)額外空間，因此空間復(fù)雜度為 O(1)

三個(gè)反置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)建了個(gè)數(shù)組，數(shù)組的空間復(fù)雜度為O(N)
空間復(fù)雜度一般只會(huì)出現(xiàn)O(1),O(N),O(N^2)，在復(fù)雜度中，還是更看重時(shí)間復(fù)雜度

以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)基石之時(shí)間與空間復(fù)雜度詳解的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言時(shí)間復(fù)雜度與空間復(fù)雜度的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論