目錄

時(shí)間復(fù)雜度

什么是時(shí)間復(fù)雜度

常見時(shí)間復(fù)雜度類型

如何計(jì)算時(shí)間復(fù)雜度

空間復(fù)雜度

什么是空間復(fù)雜度

常見的空間復(fù)雜度類型

如何計(jì)算空間復(fù)雜度

---

時(shí)間復(fù)雜度和空間復(fù)雜度是評估算法性能的兩個(gè)重要指標(biāo)。

時(shí)間復(fù)雜度

什么是時(shí)間復(fù)雜度

時(shí)間復(fù)雜度描述了算法執(zhí)行所需時(shí)間隨輸入規(guī)模增長的變化趨勢。它通常用大O表示法來描述，表示算法在最壞情況下的時(shí)間性能。

常見時(shí)間復(fù)雜度類型

• 常數(shù)時(shí)間：O(1)。算法執(zhí)行時(shí)間不隨輸入規(guī)模的變化而變化。
• 線性時(shí)間：O(n)。算法執(zhí)行時(shí)間與輸入規(guī)模成正比。
• 平方時(shí)間：O(n^2)。算法執(zhí)行時(shí)間與輸入規(guī)模的平方成正比，通常見于嵌套循環(huán)。
• 對數(shù)時(shí)間：O(logn)。算法執(zhí)行時(shí)間隨輸入規(guī)模的增長而緩慢增加，常見于分治和二分查找算法。
• 線性對數(shù)時(shí)間：O(nlogn)。算法執(zhí)行時(shí)間是輸入規(guī)模與對數(shù)的乘積，常見于快速排序或歸并排序。
• 指數(shù)時(shí)間：O(2^n)。算法執(zhí)行時(shí)間隨輸入規(guī)模指數(shù)增長，常見于暴力搜索。

在大O表示法中，logn一般指的是以2為底的對數(shù)，因?yàn)榻^大部分都只用考慮二分的情況，以其他數(shù)為底的情況很少出現(xiàn)。

如何計(jì)算時(shí)間復(fù)雜度

exp.1

//Func1的時(shí)間復(fù)雜度為O(N)
void Func1(int N)
{int i = 0;int count = 0;for (i = 0; i < N; i++){++count;}int m = 10;while (m){--m;}printf("%d\n",count);
}

該函數(shù)的運(yùn)行時(shí)間主要跟輸入的N的大小有關(guān)，故為O(n)的時(shí)間。

至于說下面的執(zhí)行的m次循環(huán)，我們是不用理會(huì)的，因?yàn)樵谳斎氲腘很大的情況，m次循環(huán)可以被忽略掉。我們算時(shí)間復(fù)雜度都是關(guān)注主要最主要的部分，比如說O(n^2 + 2n)， 那么時(shí)間復(fù)雜度是O(n^2)。

exp.2

//Func2的時(shí)間復(fù)雜度為O(N)
void Func2(int N)
{int count = 0;int i = 0;for (i = 0; i < N; i++){++count;}for (i = 0; i < N; i++){++count;}printf("%d\n",count);
}

這里咋一看時(shí)間復(fù)雜度是O(2n)，但其實(shí)時(shí)間復(fù)雜度還是O (n)。

計(jì)算機(jī)運(yùn)行的時(shí)間是非常快的，所以即使n非常大，n的常系數(shù)對于整個(gè)函數(shù)的運(yùn)行時(shí)間是微乎其微的。

所以算時(shí)間復(fù)雜度也不用算n的常系數(shù)。

exp.3

//Func3的時(shí)間復(fù)雜度為O(1)
void Func3()
{int count = 0;int i = 0;for (i = 0; i < 100; i++){++count;}printf("%d\n",count);
}

時(shí)間復(fù)雜度為O(1)，因?yàn)槭浅?shù)次運(yùn)行。

exp.4

// BubbleSort的時(shí)間復(fù)雜度為O(N^2)
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;}
}

外層循環(huán)執(zhí)行n次，內(nèi)層循環(huán)執(zhí)行n-1次、n-2次...等，等差乘等比，最會(huì)算出來會(huì)有n^2，所以時(shí)間復(fù)雜度是O(n^2)。

exp.5

// BinarySearch的時(shí)間復(fù)雜度O(logN)
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);//使用右移操作符相當(dāng)于除以2if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid;elsereturn mid;}return -1;
}

二分查找的時(shí)間復(fù)雜度是O(logn)，就是對n取以二為底的對數(shù)。

exp.6

// 階乘遞歸Fac的時(shí)間復(fù)雜度為O(N)
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

遞歸的次數(shù)同樣也算進(jìn)時(shí)間復(fù)雜度，這里遞歸了n次，所以時(shí)間復(fù)雜度是O(n)。

這里的空間復(fù)雜度也是O(n)，因?yàn)檫f歸調(diào)用函數(shù)會(huì)在棧上多開n塊額外的空間。

exp.7

// 斐波那契遞歸Fib的時(shí)間復(fù)雜度為O(2^N)
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

以這種方法算斐波那契數(shù)列的遞歸調(diào)用次數(shù)，有點(diǎn)類似算完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)。

所以時(shí)間復(fù)雜度是O(2^n)。

總結(jié)

時(shí)間復(fù)雜度只需大概想想執(zhí)行次數(shù)n的表達(dá)式，取次數(shù)最大的那項(xiàng)，也不用理會(huì)n的常系數(shù)。

如果涉及遞歸，要想想遞歸函數(shù)的執(zhí)行次數(shù)。

空間復(fù)雜度

什么是空間復(fù)雜度

空間復(fù)雜度描述了算法執(zhí)行過程中所需的額外存儲(chǔ)空間量，也用大O表示法來描述。

常見的空間復(fù)雜度類型

• 常數(shù)空間：O(1)。算法使用固定數(shù)量的額外空間，與輸入規(guī)模無關(guān)。
• 線性空間：O(n)。算法使用的額外空間與輸入規(guī)模成正比。
• 平方空間：O(n^2)。算法使用的額外空間與輸入規(guī)模的平方成正比。
• 對數(shù)空間：O(logn)。算法使用的額外空間隨輸入規(guī)模的增長而緩慢增加。
• 線性對數(shù)空間：O(nlogn)。算法使用的額外空間是輸入規(guī)模與對數(shù)的乘積。

如何計(jì)算空間復(fù)雜度

exp.1

//sum的空間復(fù)雜度是O(1)
int sum(int n) {int sum = 0;for (int i = 0; i < n; i++) {sum += i;}return sum;
}

sum只額外開辟變量sum，額外開辟的空間跟輸入的n無關(guān)，所以空間復(fù)雜度是O(1)

exp.2

//Func的空間復(fù)雜度是O(n)
void Func(int n)
{int* arr = (int*)malloc(sizeof(int) * n);//....}

Func使用的空間復(fù)雜度是O(n)，因?yàn)轭~外開辟的空間與n成正比。

總結(jié)

計(jì)算空間復(fù)雜度只需看使用的額外存儲(chǔ)空間與輸入數(shù)據(jù)規(guī)模大小的關(guān)系，比如，跟規(guī)模無關(guān)就是O(1)，跟規(guī)模成正比就是O(n)，其他O(n^2)等同理。

---

拜拜，下期再見😏

摸魚ing😴?🎞