資料結構之時間複雜度和空間複雜度

語言: CN / TW / HK

小知識,大挑戰!本文正在參與“  程式設計師必備小知識  ”創作活動

本文同時參與 「掘力星計劃」  ,贏取創作大禮包,挑戰創作激勵金

前言:🛫初來掘金!歡迎大佬們支援!相互學習,相互成長!

時間複雜度

概念

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

即:找到某條基本語句與問題規模N之間的數學表示式,就是算出了該演算法的時間複雜度


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

```

🛺時間複雜度的函式式:

F(N) = NN+2N +10

  • 當N = 10時:F = 130
  • 當N = 100時 F =10210
  • 當N = 1000時 F = 1002010

N越大,後兩項對結果的影響越小

所以:時間複雜度為:O(N^2)


大O的漸進表示法

🚓 實際中我們計算時間複雜度時,我們其實並不一定要計算精確的執行次數,而只需要大概執行次數,那麼這\ 裡我們使用大O的漸進表示法

🚐大O符號(Big O notation):是用於描述函式漸進行為的數學符號。

  • 1、用常數1取代執行時間中的所有加法常數。
  • 2、在修改後的執行次數函式中,只保留最高階項。
  • 3、如果最高階項存在且不是1,則去除與這個專案相乘的常數(係數)。得到的結果就是大O階

🛴通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項,簡潔明瞭的表>示出了執行次數。 另外有些演算法的時間複雜度存在最好、平均和最壞情況:\ 最壞情況:任意輸入規模的最大執行次數(上界)\ 平均情況:任意輸入規模的期望執行次數\ 最好情況:任意輸入規模的最小執行次數(下界)


例如 在一個長度為N陣列中搜索一個數據x\ 最好情況:1次就找到了\ 最壞情況:N次找到/找不到\ 平均情況:N/2次找到


空間複雜度

概念

🚖空間複雜度也是一個數學表示式,是對一個演算法在執行過程中臨時佔用(額外開闢)儲存空間大小的量度 。\ 空間複雜度不是程式佔用了多少bytes的空間,因為這個也沒太大意義,所以空間複雜度算的是變數的個數。\ 空間複雜度計算規則基本跟實踐複雜度類似,也使用大O漸進表示法。

注意:函式執行時所需要的棧空間(儲存引數、區域性變數、一些暫存器資訊等)在編譯期間已經確定好了,因此空間複雜度主要通過函式在執行時候顯式申請的額外空間來確定。


經典名句:空間是可以重複利用的,但是時間是一去不復返的


時間複雜度和空間複雜度就介紹到這裡啦,下一篇文章,筆者將會帶來例題講解,如果對你有所幫助的話,歡迎三連支援一下博主!歡迎各位大佬批評指正!