目錄

本章重點

一 時間復雜度

2.1?時間復雜度的概念

2.2?大O的漸進表示法

2.3?常見的時間復雜度的計算

二 空間復雜度

三 常見復雜度對比

四 復雜度的oj練習

4.1?消失的數(shù)字

4.2?旋轉(zhuǎn)數(shù)字

每一天都是人生限定，每一天都值得100%努力

本章重點

（1）算法效率（2）時間復雜度（3）空間復雜度（4）常見的時間復雜度以及復雜度oj練習

? 衡量一個算法的好壞，是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。時間復雜度主要衡量一個算法運行的快慢，空間復雜度主要衡量一個算法運行所需要的額外空間。

一 時間復雜度

2.1?時間復雜度的概念

? 算法的時間復雜度是一個函數(shù)（指的是數(shù)學函數(shù)），算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	//N*N
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	//2*N
	int M = 10;
	while (M--)
	{
		++count;
	}
	//M=10
	printf("%d\n", count);
}

（1）時間復雜度表達式為：F（N） = N*N+2 * N + 10
（2）大O漸進表示法：O(N^2)

這個函數(shù)的基本操作次數(shù)是：F（N） = N*N+2 * N + 10，隨著N的增大，后兩項對整個影響的結(jié)果變可以忽略不計小。當N無限大的時候，后兩項對結(jié)果的影響

2.2?大O的漸進表示法

4.另外有些算法的時間復雜度存在最好、平均和最壞情況： 最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界) ；平均情況：任意輸入規(guī)模的期望運行次數(shù) ；最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)；在實際中一般情況關(guān)注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為O(N)

2.3?常見的時間復雜度的計算

代碼一：

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

時間復雜度為O（1）【因為大O的漸進表示法的第一條用常數(shù)1取代運行時間中的所有加法常數(shù)。】（我們可以看到執(zhí)行次數(shù)為100）（所以，看到大O的漸進表示法，并不是讓我們只能執(zhí)行一次）（常數(shù)都是1）

代碼二：

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

時間復雜度為O(N)[大O的漸進表示法，第三條：如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階?！緦嶋H的執(zhí)行次數(shù)是：2*N+10】

代碼三：

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

時間復雜度為O(N+M);如果給出N遠大于M，就可以寫成O(N)；如果給出N和M差不多就可以寫成O(N)或者O(M)；該代碼什么都沒有給，所以就是O(M+N)；

代碼4

const char* strchr(const char* str, int character)
{
	while (*str)
	{
		if (*str == character)
			return str;
		else
			++str;
	}
	return NULL;
}

時間復雜度為O(N)；因為不確定什么時候被找到，第四條：在實際中一般情況關(guān)注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為O(N)

關(guān)于時間復雜度，我們要準確分析時間復雜度，一定要去看思想，不能僅僅去看程序是幾層循環(huán)，主要是要看代碼的思想。比如：冒泡排序（O(N^2)），就是N-1,N-2,N-3……2,1,是一個等差數(shù)列（N-1+1）(N-1)/2=N(N-1)【這是最差情況】，N-1【最好的情況】。

二分查找的時間復雜度：O(㏒?N )【最好的情況：O(1)一次找到；? 最差的情況(找不到的情況）：O(log2 N )? ?（1*2*2*2…2)^X(次）= N(從找不到的時候，向前思想】

時間復雜度，會把O（㏒?N）簡寫成O(logN).有些書籍也會寫成O(lgN)（這個是不正規(guī)的）

代碼5

long long Fac(size_t N)
{//階乘
	if (0 == N)
		return 1;

	return Fac(N - 1) * N;
}

時間復雜度為O(N)，；實際上是N+1

代碼6

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	for (size_t i = 0; i < N; ++i)
	{
		printf("%d", i);
	}
	printf("\n");

	return Fac(N - 1) * N;
}

時間復雜度為O(N^2)，；實際上是(N-1)+（n-2）+……+1+0

遞歸算法的時間復雜度：1、每次函數(shù)調(diào)用如果是是O(1)，那么就看他的遞歸次數(shù)（遞歸次數(shù)是多少，時間復雜度就是多少)（代碼5）

2、如果不是O(1)，那么就看他的遞歸調(diào)用次數(shù)的累加（每次遞歸，函數(shù)調(diào)用的累加）（代碼6）

代碼7

long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}
//斐波那契數(shù)列
//符合遞歸算法的第一種

?時間復雜度為O(2^N)，第一層調(diào)用一次，第二層?調(diào)用2次，第三層調(diào)用4次?，一直到Fib（3）分成Fib（2）+Fib（1），那就是N-1層（假設每一層都是滿的，起始并不是每一層都是滿的），那最后一層就是2^(N-1)，然后就是等比數(shù)列相加，就是(2^n-1)-1,

二 空間復雜度

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;
	}
}

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;
}

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

long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

三 常見復雜度對比

一些常見的復雜度

四 復雜度的oj練習

4.1?消失的數(shù)字

數(shù)組nums包含從0到n的所有整數(shù)，但其中缺了一個。請編寫代碼找出那個缺失的整數(shù)。(時間復雜度為O(N)

輸入：[3,0,1]輸出：2；?

思路一:先排序，然后進行遍歷（冒泡O(N^2），看是否是前一個數(shù)字+1得到的值（但是時間復雜度不符合題意）

思路二:映射方式（首先定義一個數(shù)組，里面的值全部賦值成-1，然后輸入的數(shù)組，每一個值是多少，就作為下標對應的位置寫多少）（時間復雜度為：O(N)）

思路三:異或（用一個val和0-N的數(shù)字異或，再和數(shù)據(jù)中的數(shù)字異或，最后cal中得知就是缺失的值）（O(N)）

思路三:等差數(shù)列(O(N))

代碼1展示：（思路三）函數(shù)接口型

int missingNumber(int* nums, int numsSize){
    int x = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        x ^= nums[i];
    }
    for (int i = 0; i < numsSize + 1; ++i)
    {
        x ^= i;
    }
    return x;

}

4.2?旋轉(zhuǎn)數(shù)字

給定一個整數(shù)數(shù)組?nums，將數(shù)組中的元素向右輪轉(zhuǎn)?k?個位置，其中?k?是非負數(shù)。輸入: nums = [1,2,3,4,5,6,7], k = 3輸出: [5,6,7,1,2,3,4]解釋:向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

思路一:右旋K次（每次右旋一次）【時間復雜度為O(N*K)；空間復雜度為O(1)】（時間復雜度的k最大為N-1），最壞的結(jié)果為O(N^2)）

思路二:開設一個新的數(shù)組，把后k個放到新數(shù)組的前面，前面的依次放到后面【時間復雜度O(N),空間復雜度O(N)】?(這種方法比第一種，就是時間換取空間的算法）

思路三:三趟逆置【時間復雜度為O(N)，空間復雜度為O(1)】

(思路一和思路三在C語言進階欄目-C進階習題里面有詳細說明 http://t.csdn.cn/sFLCM）

思路三：（函數(shù)接口型）文章來源地址http://www.zghlxwxcb.cn/news/detail-790089.html

void reverse(int* arr,int left, int right)
{
    while (left < right)
    {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        ++left;
        --right;
    }
}
void rotate(int* nums, int numsSize, int k){
    int m = k % numsSize;
    reverse(nums, 0, numsSize - m - 1);
    reverse(nums, numsSize - m, numsSize - 1);
    reverse(nums, 0, numsSize -1);
}

到了這里，關(guān)于算法的時間復雜度和空間復雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！