被富豪注意了，我趕緊寫下時空復雜度這篇文章

聯動文章 身價過億的女王對小碼農說中斷會了嗎

什么是資料結構

就是實作一些專案，需要在記憶體中將資料存盤起來

演算法的時間復雜度和空間復雜度

1.演算法效率

2.時間復雜度

3.空間復雜度

4.常見的時間復雜度以及復雜度oj練習

1.演算法效率

如何衡量一個演算法的好壞

比如下面的斐波那契數列

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

演算法的復雜度

演算法在撰寫成可執行程式后，運行時需要耗費時間資源和空間(記憶體)資源 ，因此衡量一個演算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度，
==時間復雜度主要衡量一個演算法的運行快慢，而空間復雜度主要衡量一個演算法運行所需要的額外空間，==在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，

時間復雜度

時間復雜度的概念

時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，

注意：

1.這里的函式是數學中帶有未知數的函式運算式，

2.并且我們說的時間不是秒，而是幾次幾次的意思

因為機器不同（有的2核，有的一核），具體的運行時間就不同，所以沒辦法用時間來衡量時間復雜度

// 請計算一下Func1中++count陳述句總共執行了多少次？
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);
}

實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法，

大O的漸進表示法

大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，

推導大O階方法：

1.用常數1取代運行時間中的所有加法常數

2.在修改后的運行次數函式中，只保留最高階項，

3.如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階

另外有些演算法的時間復雜度存在最好，平均和最壞情況

==最壞情況：==任意輸入規模的最大運行次數（上界）

==平均情況：==任意輸入規模的期望運行次數

==最好情況：==任意輸入規模的最小運行次數(下屆)

在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)

實體

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

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

例3

// 計算Func4的時間復雜度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

例4

// 計算strchr的時間復雜度？
const char* strchr(const char* str, int character);

例5

#include<stdio.h>
// 計算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;
	}
}

例6

算時間復雜度不能只去看幾層回圈，而要去看他的思想

// 計算BinarySearch的時間復雜度？
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;
		else
			return mid;
	}
	return -1;
}

例7

#include<stdio.h>
// 計算階乘遞回Fac的時間復雜度？
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}

例8

我們要知道時間復雜度的時間是不復用的

#include<stdio.h>
// 計算斐波那契遞回Fib的時間復雜度？
long long Fib(size_t N)
{
  if (N < 3)
      return 1;
  return Fib(N - 1) + Fib(N - 2);
}

空間復雜度

空間復雜度也是一個數學運算式，是對一個演算法在運行程序中==臨時占用額外存盤空間大小的量度 ，==空間復雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法

注意：

函式運行時所需要的堆疊空間(存盤引數、區域變數、一些暫存器資訊等)在編譯期間已經確定好了，因此空間復雜度主要通過函式在運行時候顯式申請的額外空間來確定，

實體

例1

#include<stdio.h>
// 計算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;
	}
}

例2

#include<stdio.h>
// 計算Fibonacci的空間復雜度？
// 回傳斐波那契數列的前n項
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;
}

例3

堆疊幀的消耗看遞回的深度

#include<stdio.h>
// 計算階乘遞回Fac的空間復雜度？
long long Fac(size_t N)
{
	if (N == 0)
		return 1;
	return Fac(N - 1) * N;
}

堆疊并不是很大

例4

空間是可以重復利用，不累計的，時間是不復用的，累計的，這句話是時間復雜度，空間復雜度的精髓

#include<stdio.h>
// 計算斐波那契遞回Fib的空間復雜度？
long long Fib(size_t N)
{
  if (N < 3)
      return 1;
  return Fib(N - 1) + Fib(N - 2);
}

常見的復雜度對比

復雜度的OJ練習

1.消失的數字

**思路一：**這道題很多人想法就是排序然后從小到大再去遍歷 qsort快排–》時間復雜度O(N*log2N)，明顯不滿足條件

**思路二：**這個思路和陣列下標聯合起來了，陣列用的好基本也是奇計，（0+1+2+…+n）-（nums[0]+nums[1]+nums[2]+…+nums[n-1]）

**思路三：**還有就是很類似上面那個思路，創建一個（n+1）陣列

**思路四：**谷歌面試題考過類似的 創建一個變數x=0，讓x與[0,n]全都異或一遍，再和，陣列里面的異或一遍，然后再后個數異或一遍，最后得到的x就是我們缺的數 我們知道兩個相同的數異或就沒了

2.旋轉陣列

你們發現了嗎哈哈思路一永遠都是高校學生的做法，永遠都是暴力求解，簡單粗暴法

**思路一：**暴力求解旋轉k次 時間復雜度是O(N*K) 空間復雜度O(1)

**思路二：**開辟額外的空間，用空間來換取時間，這也是比較好的方法 時間復雜度O(N) 空間復雜度O(N)，但是不符合題目要求，空間超過了

**思路三：**很牛逼，在《程式員的基本修養》上面好像有這道題三步翻轉，前面翻轉，后面翻轉，然后整體翻轉大牛想出的高效方法

時間復雜度O(N) 空間復雜度O(1)

聯動文章 身價過億的女王對小碼農說中斷會了嗎