目錄
- 前言
- 時間復雜度
- 概念
- ?O的漸進表?法
- 小試牛刀
- 空間復雜度
前言
要想知道什么是空/時間復雜度,就得知道什么是數據結構。
這得分兩層來理解。我們生活中處處存在數據，什么抖音熱點上的國際大事，什么懂的都懂的雍正卸甲等等一系列我們用戶看得到的，就是抖音存儲在后臺服務器的數據。但這些數據都有一個特點，那就是都在抖音的熱搜榜單上，而這個榜單就是結構，保證數據在一個固定的位置里以便用戶瀏覽。
此外有了數據結構，就離不開算法。那么我們剛剛說了，數據結構是把數據有規律的存儲在一個結構中，那么怎么從結構中有效率的存取數據，這就是算法。
時間復雜度
有了算法，就存在時間復雜度和空間復雜度。因為計算機現在的內存越來越大，所以時間復雜度比空間復雜度更顯得重要。所以我們先來了解時間復雜度
概念
時間復雜度，最重要的詞就是時間，這里的時間就是指一個程序運行時的時間，如果時間復雜度越少，那么證明這個算法越好。時間復雜度計算用函數式T(N)表示
那為什么我們不提前算出這個程序的時間復雜度來寫出最優解的代碼呢？這里就涉及到計算機的問題。
- 因為程序運?時間和編譯環境和運?機器的配置都有關系，?如同?個算法程序，??個?編譯
器進?編譯和新編譯器編譯，在同樣機器下運?時間不同。- 同?個算法程序，??個?低配置機器和新?配置機器，運?時間也不同。
- 并且時間只能程序寫好后測試，不能寫程序前通過理論思想計算評估。
下面我們來看一段代碼:
// 請計算?下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;
}
}
這段代碼如果根據count的執行次數來看的話應該是:
T (N) = N2 + 2 ? N + 10
? N = 10 T(N) = 130
? N = 100 T(N) = 10210
? N = 1000 T(N) = 1002010
這時候有人就說，那個int count=0不算嗎;
這里我們就太小看我們的計算機了，我們計算機一秒鐘cpu可以執行上億次，這小小的一次當然可以忽略不計。所以說我們計算的時間復雜度并不準確，只是粗略估計而已，這時候我們就用一個新的符號表示.
?O的漸進表?法
?O符號（Big O notation）：是?于描述函數漸進?為的數學符號;這里用來表示估算的時間復雜度。
那么這里還是跟T(N)一樣算嗎，如果是這樣我們就沒必要用另外一個符號來表示了。這里就涉及到算O的規則:
- 時間復雜度函數式T(N)中，只保留最?階項，去掉那些低階項，因為當N不斷變?時，低階項對結果影響越來越?，當N?窮?時，就可以忽略不計了。
- 如果最?階項存在且不是1，則去除這個項?的常數系數，因為當N不斷變?，這個系數對結果影響越來越?，當N?窮?時，就可以忽略不計了
- T(N)中如果沒有N相關的項?，只有常數項，?常數1取代所有加法常數。
那么再來看上面的T(N)=N^ 2 + 2 ? N + 10,這里的最高階是N2所以去掉其他的低階，復雜度就為(ON^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);
}
這里的T(N)=M+N，那我們再來算O(N),這里M和N都是同階，所以不符合第一條規則，也沒有對應第二條和第三條，所以為o(N+M)，那么有人就問了，萬一N比M大呢，是不是因該是O(N).這里問題就是，你怎么知道N比M大？萬一是M比N大呢，所以保險起見我們都留下來。
// 計算strchr的時間復雜度？
const char * strchr ( const char* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}
這里我們是查找character在str中的位置，這里我補充一個知識點:
- 我們的O算的一般是一個算法的最壞情況下的復雜度
這里就可以分為三個復雜度:
1.最好情況
若要查找的字符在字符串第?個位置，則：
F (N) = 1,復雜度為o(1)
2.平均情況:
若要查找的字符在字符串中間位置，則：
F (N) = N/2,O(N/2)
3.最壞情況
若要查找的字符在字符串最后的?個位置，則：
F (N) = N,O(N)
// 計算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;
}
}
最壞情況下，又因為保留高階去掉n/2(第一條),忽略系數(第二條)，所以為ON^2
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
當n=2時，執?次數為1
當n=4時，執?次數為2
當n=16時，執?次數為4
假設執?次數為 x ，則 2
x = n
因此執?次數： x = log n
因此：func5的時間復雜度取最差情況為：
O(log2 ^n)
不同書籍的表??式不同，以上寫法差別不?，我們建議使? log n
空間復雜度
空間復雜度要注意的是，他的計算表示也是用O來表示，并且他的規則與時間復雜度一樣遵守那三條規則
注意
函數運?時所需要的棧空間(存儲參數、局部變量、?些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運?時候顯式申請的額外空間來確定
例1:
// 計算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;
}
}
函數棧幀在編譯期間已經確定好了，
只需要關注函數在運?時額外申請的空間。
BubbleSort額外申請的空間有
exchange等有限個局部變量，使?了常數個額外空間
因此空間復雜度為 O(1)
】)
)
