文章目錄
- 前言
- 一、時間復雜度和空間復雜度是什么？
- 1.1演算法效率定義
- 1.2時間復雜度概念
- 1.3空間復雜度概念
- 二、如何計算常見演算法的時間復雜度和空間復雜度
- 2.1引例
- 2.2快速推倒大O漸進表達法
- 三、一些特殊的情況
- 總結
前言
我們在進行編程時，往往會開發諸多的演算法，那么我們怎么在那么多演算法中找到最好的那個呢？這便是我們今天的學習，時間復雜度和空間復雜度，本文主要介紹時間和空間復雜度概念及時間復雜度的求解，對于空間復雜度的求解會放在篇2進行講解，預祝讀者學習愉快
提示：以下是本篇文章正文內容，下面案例可供參考
一、時間復雜度和空間復雜度是什么？
1.1演算法效率定義
演算法效率分為兩種，一種是時間效率——時間復雜度，另一種是空間效率——空間復雜度
1.2時間復雜度概念
時間復雜度，簡言之就是你寫一個代碼，它解決一個問題上需要走多少步驟，需要花費多長時間，打個簡單的比方：現在給10個數，要求找到7在哪里1,2,3,4,5,6,7,8,9,10，我們要求寫一個代碼，同學狗蛋寫了一個暴力查找，從第一個數依次往后遍歷，他的演算法要找7次，同學狗剩寫了一個二分法查找，只要找2次，這就是時間復雜度的比較
演算法中的基本操作的執行次數，為演算法的時間復雜度
1.3空間復雜度概念
空間復雜度，是對一個演算法在運行程序中臨時占用存盤空間大小的量度，舉個栗子：我們現在要求寫一個代碼，狗蛋啪啪啪敲了一大堆變數，程式運行了，狗剩就用了很少的變數，程式也運行了，但是他們兩個在代碼運行中變數多少不同，占用的記憶體多少是不一樣的，空間復雜度，它計算的是變數的個數，
二、如何計算常見演算法的時間復雜度和空間復雜度
我們在計算時間/空間復雜度時用的都是大O漸進表示法（是一種估演算法）
2.1引例
我們以一個簡單的函式舉例
代碼如下：
void func1(int n)
{
int i = 0;
int j = 0;
int k = 0;
int count = 0;
for (i = 0;i < n;i++)
{
for (j = 0;j < n;j++)
{
count++;
}
}
for (k = 0;k < 3 * n - 1;k++)
{
count++;
}
}
試問：該函式如果被呼叫，要運行多少次？
我們清楚的看出i進去有n次，共有n個i，第一個for結束要運行n^ 2次，第二個for要執行3n-1次，共執行n^ 2+3n-1次
那么我們這里的時間復雜度是否就是n^2+3n-1呢？答案是否的
我們前面說過，時間復雜度和空間復雜度用的都是大O漸進表示法，是一種估演算法，我們取的值，是取對運算式中影響最大的那個，我們仍以n^ 2+3 * n-1這個式子進行舉例：設f(n)=n^2+3n-1
n=1,f(n)=1+3-1=3
n=10,f(n)=100+30-1=129
n=100,f(n)=10000+300-1=10299
n=1000,f(n)=1002999
…
很容易發現，對f(n)影響最大的是n^ 2,設g（n）=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000
…
當n越大，g（n）就越接近f（n）
那么這里的時間復雜度大O漸進表達法寫法是這樣的：O(n^2)
2.2快速推倒大O漸進表達法
1.常數1代替所有加法運算中的常數
2.只保留最高階（高數極限思想）
3.若最高階存在且不為常數，則去除最高階的系數，比如3*n^ 9，去掉系數變為n^9
我們再來看兩個代碼訓練一下
代碼1如下：
void func2(int n)
{
int i = 0;
int k = 0;
int count = 0;
for (i = 0;i < 3n;i++)
{
count++;
}
for (k = 0;k < 6;k++)
{
count++;
}
}
這里f（n）=3n+6，它的大O漸進表達法就是O（n）
代碼2如下：
void func3(int n)
{
int i = 0;
int count = 0;
for (i = 0;i < 1000;i++)
{
count++;
}
}
這里一眼就看出是運行1000次，用什么來表示呢？前面說過：常數1代替所有加法運算中的常數，所以這里不管常數有多大，只要你只有一個常數都用O(1)表示
一些注意事項：
O(1)這個時間復雜度的估值是不隨n的改變而改變的，以大白話說，不管你輸入的n是多少，我這個演算法的效率是不變的
O(n)這個時間復雜度是隨n改變的
打個通俗的比方：設一個函式O(x)=1,那你x隨意多少，函式值都是1
設一個函式O(X)=x，那這里函式值就隨x變換而變換了
三、一些特殊的情況
有些演算法的時間復雜度是存在最好、平均、最壞情況：
最壞情況：任意輸入規模的最大運行次數（上界）
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數（下界）
不多說，舉例說明：
代碼如下：
const char*strchr(char*str, char c)
{
while (*str != '\0')
{
if (*str == c)
{
return str;
}
++str;
}
return NULL;
}
上面的代碼是一個簡單的查找字符的函式，比如我們現在給一串字符共n個字符“aaaaba…aaac”（省略號省略a）
這里查找a一下子就找到了，查找b要點功夫，查找c就更慢了，如果查找d，不好意思，查無此d，
那么這里就出現了最好情況：一次找到O（1）
平均情況：O（n/2）
最差情況：O（n）
對于這里最壞情況可能有同學要說為什么是O（n），你看最壞情況沒找到不是嗎？這里解釋是這樣的，你找c要n次，找d是找不到也要找n次才能確定找不到，
總結
本文介紹了時間和空間復雜度的定義及大O漸進表達法的演算法及一些特殊情況的解釋，希望對螢屏前的讀者有所幫助，祝您學習愉快！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298363.html
標籤：其他
下一篇：[C語言]結構體