当前位置:网站首页>身家過億的帝都富豪對小碼農說你時空複雜度會了嗎

身家過億的帝都富豪對小碼農說你時空複雜度會了嗎

2021-10-14 08:06:55 小碼農UU

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

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

什麼是數據結構

就是實現一些項目,需要在內存中將數據存儲起來

算法的時間複雜度和空間複雜度

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

image-20211010190548808

實際中我們計算時間複雜度時,我們其實並不一定要計算精確的執行次數,而只需要大概執行次數,那麼這裏我們使用大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);
}

image-20211010192257554

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

image-20211010193507709

例3

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

image-20211010194233192

例4

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

image-20211010202110950

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

image-20211010203746705

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

image-20211012081305608

例7

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

image-20211012082935548

例8

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

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

image-20211012123848021

空間複雜度

空間複雜度也是一個數學錶達式,是對一個算法在運行過程中==臨時占用額外存儲空間大小的量度 。==空間複雜度不是程序占用了多少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;
	}
}

image-20211012104906697

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

image-20211012130110575

例3

棧幀的消耗看遞歸的深度

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

image-20211012141720594

棧並不是很大

image-20211012143230921

例4

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

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

image-20211012145011757

常見的複雜度對比

image-20211012145219139

複雜度的OJ練習

1.消失的數字

image-20211012145801538

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

**思路二:**這個思路和數組下標聯合起來了,數組用的好基本也是奇計,(0+1+2+…+n)-(nums[0]+nums[1]+nums[2]+…+nums[n-1])

image-20211012154951079

**思路三:**還有就是很類似上面那個思路,創建一個(n+1)數組

image-20211012155611491

**思路四:**穀歌面試題考過類似的 創建一個變量x=0,讓x與[0,n]全都异或一遍,再和,數組裏面的异或一遍,然後再後個數异或一遍,最後得到的x就是我們缺的數 我們知道兩個相同的數异或就沒了

image-20211012164629597

2.旋轉數組

image-20211012165755410

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

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

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

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

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

image-20211012175046826

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

版权声明
本文为[小碼農UU]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/10/20211014080136779v.html

随机推荐