數(shù)據(jù)結(jié)構(gòu) | 算法的時(shí)間復(fù)雜度和空間復(fù)雜度【詳解】
1. 什么是數(shù)據(jù)結(jié)構(gòu)？
數(shù)據(jù)結(jié)構(gòu)(Data Structure)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
2. 什么是算法？
算法(Algorithm):就是定義良好的計(jì)算過(guò)程，他取一個(gè)或一組的值為輸入，并產(chǎn)生出一個(gè)或一組值作為輸出。簡(jiǎn)單來(lái)說(shuō)算法就是一系列的計(jì)算步驟，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)化成輸出結(jié)果。
3. 算法效率
-
算法效率是指算法執(zhí)行的時(shí)間，算法執(zhí)行時(shí)間需通過(guò)依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來(lái)度量。在現(xiàn)在的計(jì)算機(jī)硬件環(huán)境中，比較少需要考慮這個(gè)問(wèn)題了，特別是pc機(jī)的編程，內(nèi)存空間越來(lái)越大，所以被考慮得也越來(lái)越少，不過(guò)一個(gè)好的程序員，都應(yīng)該對(duì)自己的程序有要求，每一個(gè)for比別人少一次判斷1000個(gè)for就能夠少掉很多的運(yùn)行時(shí)間。所以能夠理解，能夠大概的去運(yùn)用"效率度量"還是有很大意義的。 -
算法在編寫(xiě)成可執(zhí)行程序后，運(yùn)行時(shí)需要耗費(fèi)時(shí)間資源和空間(內(nèi)存)資源 。因此衡量一個(gè)
算法的好壞，一般是從時(shí)間和空間兩個(gè)維度來(lái)衡量的，即時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢，而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。在計(jì)算 機(jī)發(fā)展的早期，計(jì)算機(jī)的存儲(chǔ)容量很小。所以對(duì)空間復(fù)雜度很是在乎。但是經(jīng)過(guò)計(jì)算機(jī)行業(yè)的迅速發(fā)展，計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度。
4. 時(shí)間復(fù)雜度
4.1 時(shí)間復(fù)雜度的概念
- 時(shí)間復(fù)雜度的定義：
- 在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。一 個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上說(shuō)，是不能算出來(lái)的，只有你把你的程序放在機(jī)器上跑起來(lái)，才能知道。但是我們需要每個(gè)算法都上機(jī)測(cè)試嗎？是可以都上機(jī)測(cè)試，但是這很麻煩，所以才有了時(shí)間復(fù)雜度這個(gè) 分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為
算法的時(shí)間復(fù)雜度。
- 在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。一 個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上說(shuō)，是不能算出來(lái)的，只有你把你的程序放在機(jī)器上跑起來(lái)，才能知道。但是我們需要每個(gè)算法都上機(jī)測(cè)試嗎？是可以都上機(jī)測(cè)試，但是這很麻煩，所以才有了時(shí)間復(fù)雜度這個(gè) 分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為
即：找到某條基本語(yǔ)句與問(wèn)題規(guī)模N之間的數(shù)學(xué)表達(dá)式，就是算出了該算法的時(shí)間復(fù)雜度。
實(shí)際中我們計(jì)算時(shí)間復(fù)雜度的時(shí)候其實(shí)并不需要計(jì)算精確的執(zhí)行次數(shù)，而只需要知道大概執(zhí)行次數(shù)，所以這里我們引入了大O的漸進(jìn)表示法。其中大O符號(hào)是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。
案例1：
請(qǐng)計(jì)算一下Func1中++count語(yǔ)句總共執(zhí)行了多少次？
- 如果用一個(gè)函數(shù)F(N)來(lái)解釋的話，怎么解釋？【F(N) = N*N + 2N + 10】這是一個(gè)
函數(shù)式
這并不方便我們進(jìn)行比較，能不能簡(jiǎn)化一下？
這里的時(shí)間復(fù)雜度是要取影響最大的項(xiàng)
大O漸進(jìn)表示法：估算–>O(N^2)–>O(N)
我們這里不關(guān)心硬件，相同的配置N比N^2的程序要快
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);
}
Func1 執(zhí)行的基本操作次數(shù) ：
- N = 10 F(N) = 130
- N = 100 F(N) = 10210
- N = 1000 F(N) = 1002010
實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進(jìn)表示法。
4.2 推導(dǎo)大O階的方法：
大 O 表示法是一種計(jì)算機(jī)科學(xué)和算法分析中常用的漸進(jìn)表示法，用于描述算法的時(shí)間復(fù)雜度和空間復(fù)雜度。它幫助我們衡量算法在輸入規(guī)模增加時(shí)，運(yùn)行時(shí)間或內(nèi)存使用的增長(zhǎng)趨勢(shì)，而不需要精確地測(cè)量或比較具體的運(yùn)行時(shí)間。
大 O 表示法使用 “O(f(n))” 的形式，其中 “f(n)” 表示輸入規(guī)模 “n” 的函數(shù)。這意味著當(dāng)輸入規(guī)模足夠大時(shí)，算法的運(yùn)行時(shí)間或內(nèi)存使用將以 “f(n)” 函數(shù)的方式增長(zhǎng)。以下是一些常見(jiàn)的大 O 表示法及其含義：
- O(1)：常數(shù)時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間不受輸入規(guī)模的影響，無(wú)論輸入有多大，運(yùn)行時(shí)間都是固定的。 - O(log n)：對(duì)數(shù)時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間以對(duì)數(shù)方式增長(zhǎng)，通常見(jiàn)于二分查找等分治算法。 - O(n)：線性時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間與輸入規(guī)模線性增長(zhǎng)，隨著輸入規(guī)模增加，運(yùn)行時(shí)間也會(huì)線性增加。 - O(n log n)：線性對(duì)數(shù)時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間隨著輸入規(guī)模的對(duì)數(shù)線性增加，常見(jiàn)于快速排序和歸并排序等算法。 - O(n^2)：二次時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間與輸入規(guī)模的平方成正比，通常見(jiàn)于嵌套循環(huán)等情況。 - O(n^k)：多項(xiàng)式時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間與輸入規(guī)模的 k 次方成正比，其中 k 為常數(shù)。 - O(2^n)：指數(shù)時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間隨著輸入規(guī)模的指數(shù)級(jí)增長(zhǎng)，通常表示算法的效率非常低。 - O(n!)：階乘時(shí)間復(fù)雜度
表示算法的運(yùn)行時(shí)間隨著輸入規(guī)模的階乘級(jí)增長(zhǎng)，通常表示算法的效率非常低。 - 大 O 表示法的目的是為了提供算法效率的一種抽象概念，讓人們能夠更容易比較不同算法的性能，并估計(jì)它們?cè)诖笠?guī)模輸入下的行為。通過(guò)了解算法的大 O 復(fù)雜度，開(kāi)發(fā)者可以選擇合適的算法來(lái)解決問(wèn)題，以便在實(shí)際應(yīng)用中獲得更好的性能。
使用大O的漸進(jìn)表示法以后，F(xiàn)unc1的時(shí)間復(fù)雜度為：
- N = 10 F(N) = 100
- N = 100 F(N) = 10000
- N = 1000 F(N) = 1000000
4.3 常見(jiàn)時(shí)間復(fù)雜度計(jì)算舉例：
接下來(lái)就看看下面這幾個(gè)案例，相信你看完就有一定的了解
實(shí)例2：
計(jì)算Func2的時(shí)間復(fù)雜度？
- 我們前期就一點(diǎn)一點(diǎn)的算，
F(N) = 2N + 10 - 時(shí)間復(fù)雜度是什么?【O(N)】
- 就是取最大的那一項(xiàng)，當(dāng)N無(wú)限大的時(shí)候
N和2N沒(méi)有區(qū)別，所以系數(shù)要去掉 - 時(shí)間復(fù)雜度不是算次數(shù)，是算量級(jí)
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);
}
實(shí)例3：
計(jì)算Func3的時(shí)間復(fù)雜度？
- 如果不確定M和N的關(guān)系，可能M很大，可能N很大–>
O(M+N)或者O(max(M,N)) - 如果N遠(yuǎn)大于M–>
O(N) - 如果M遠(yuǎn)大于N–>
O(M) - 如果N和M差不多大–>
O(N)orO(M)
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);
}
實(shí)例4：
計(jì)算Func4的時(shí)間復(fù)雜度？
- 這里可以看到k循環(huán)了100次，那么他是
O(100)嗎？【不是！】是O(1)
注意： O(1)并不是代表一次，而是常數(shù)次！
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
小結(jié)一下：
- 大O階的方法：
- 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
- 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)，取決定性的那一項(xiàng)
- 如果最高階項(xiàng)存在且系數(shù)是不唯1的常系數(shù)，則去除最高項(xiàng)的系數(shù)，得到的結(jié)果就是大O階
- 如果最終結(jié)果是O(1)，則表示常數(shù)次，并不是代表一次
- 還有就是沒(méi)有小o階~~
實(shí)例5：
計(jì)算strchr的時(shí)間復(fù)雜度？
const char* strchr(const char* str, int character);
while (*str) {
if (*str == character)
return str;
++str;
}
- 這個(gè)函數(shù)有可能有的同學(xué)沒(méi)有見(jiàn)過(guò)，這是C語(yǔ)言庫(kù)里面的一個(gè)函數(shù)strchr，是定位字符串中出現(xiàn)的第一個(gè)字符
- 可能在前面的位置找到了（最好），肯在中間的位置找到了（平均），還有肯在最后的位置找到了（最壞）
小結(jié)一下：
-
最壞情況：
- 任意輸入規(guī)模的最大運(yùn)行次數(shù)（上界）
-
平均情況：
- 任意輸入規(guī)模的期望運(yùn)行次數(shù)
-
最好情況：
- 任意輸入規(guī)模的最小運(yùn)行次數(shù)（下界）
- 一般我們比較關(guān)心的是一個(gè)算法的最壞情況
-
如果有最好，最壞，平均，那么時(shí)間復(fù)雜度是一個(gè)保守的估算，是取
最壞，這是最好的！??！
實(shí)例6：
計(jì)算BubbleSort的時(shí)間復(fù)雜度？
- 很多同學(xué)一眼看他是
O(N^2)，那么他是O(N^2)嗎？接下來(lái)接著看
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;
}
}
- 再來(lái)看一個(gè)，這個(gè)相比上一個(gè)的時(shí)間復(fù)雜度是什么？
- 可能有點(diǎn)同學(xué)一看這個(gè)循環(huán)有兩層那么他是
O(N^2),它是O(N^2)嗎？–>繼續(xù)接著往下看！
int PartSort1(int* a, int left, int right) {
int keyi = left;
while (left < right) {
while (left < right && a[right] >= a[keyi]) {
--right;
}
while (left < right && a[left <= a[keyi]]) {
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[right]);
}
我們上面都是看的循環(huán)，但是我們要看思想，不能只看循環(huán)，第一個(gè)是–>O(N^2)第二個(gè)是O(N)
你算對(duì)了嗎？
- 首先我們先看第一個(gè)冒泡排序的時(shí)間復(fù)雜度，如圖：
- 再來(lái)看第二個(gè)
PartSort1，當(dāng)left和right相遇時(shí)，時(shí)間復(fù)雜度是O(N)
小結(jié)一下：
- 時(shí)間復(fù)雜度不能數(shù)代碼中的循環(huán)
- 而是需要根據(jù)思想進(jìn)行靈活計(jì)算?。?！
實(shí)例7：
計(jì)算BinarySearch的時(shí)間復(fù)雜度？
- 這里一眼看就是一個(gè)二分查找~~
- 我們這里的是不是復(fù)雜度數(shù)
O(N)?
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號(hào)
while (begin <= end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid - 1;
else
return mid;
}
return -1;
}
- 首先先說(shuō)結(jié)論，這里是
O(logN)，我們這里看代碼是看不出來(lái)的，要看思想~~ - 首先二分查找的前提是
有序
-
這個(gè)數(shù)組假設(shè)有n個(gè)值
-
n/2/2/…/2 = 1（最壞的情況~~）
-
我們這里除了多少個(gè)2？
找了多少次就除了多少個(gè)2 -
假設(shè)找了x次–>
2^x = N-->x = logN
我們這里的這個(gè)以2為底的logN是不是很不好寫(xiě)…我們平時(shí)就可以不寫(xiě)了~~，直接寫(xiě)成
O(logN)
但是有的書(shū)或者博客上面寫(xiě)成O(lgN)，我們不建議~~，和我們數(shù)學(xué)里面是有些混淆的
學(xué)了復(fù)雜度我們要指定
O(logN)是一個(gè)很膩害的算法我們下面進(jìn)行對(duì)照~~
- 這里對(duì)應(yīng)的有暴力查找（數(shù)組過(guò)一遍查找）：
O(N) - 二分查找：
O(logN)
比如：
- 如果我把中國(guó)所有人的信息放到一個(gè)數(shù)組中，我們要找多少次？
我們就只需要找
31次，是不是很厲害~~
- 我們這里前提是要有序，有序是要有代價(jià)的，需要排序，如果有一個(gè)新生兒出生了，就要插入，如果有人離世了，就要?jiǎng)h除了，這就很難~~
- 這里有更好的數(shù)據(jù)結(jié)構(gòu)，有：AVL樹(shù)，紅黑樹(shù)，哈希表，這些我們后面都會(huì)講解~~
實(shí)例8：
計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度？
- 首先來(lái)看這是一個(gè)階乘，很多同學(xué)肯一看是
O(1)，又不太敢確認(rèn) - 我們先說(shuō)結(jié)論—>
O(N)
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
- 階乘是不是有多次函數(shù)的調(diào)用，每次調(diào)用是常數(shù)次
O(N)，有N次調(diào)用就是O(N)~~
我們?cè)賮?lái)變一下形~~，我們來(lái)看下面，這個(gè)的時(shí)間復(fù)雜度是多少呢？
- 我們先說(shuō)結(jié)果–>
O(N^2)，然后我們進(jìn)行分析~~
long long Fac(size_t N)
{
if (0 == N)
return 1;
for (size_t i = 0; i < N; ++i)
{
//....
}
return Fac(N - 1) * N;
}
- 這里是咋算的？
- 每次遞歸走了一次循環(huán)，遞歸計(jì)算的是多次調(diào)用累加，多少次調(diào)用？N次調(diào)用，每次調(diào)用多少趟？這不是N，每次都在變化，當(dāng)N為10時(shí)，循環(huán)走10次，當(dāng)N是9時(shí)，循環(huán)走9次
- 遞歸次數(shù)累加是一個(gè)等差數(shù)列
（0~N）的等差數(shù)列 - 所以就是
O(N^2)~~
實(shí)例9：
計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度？
- 斐波那契數(shù)列類似于細(xì)胞分裂，一個(gè)分裂成兩個(gè)，兩個(gè)分裂成4個(gè)…
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
- 這里仔細(xì)看，這是一個(gè)等比數(shù)列和~~
- 這里可以用到錯(cuò)位相減法，如圖：
- 根據(jù)大O漸進(jìn)表示法，時(shí)間復(fù)雜度也就是
O(2^N)，這是一個(gè)成指數(shù)增長(zhǎng)的~~
5.空間復(fù)雜度
- 空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)
額外占用存儲(chǔ)空間大小的量度?？臻g復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒(méi)太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。 - 空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用大O漸進(jìn)表示法。
- 注意： 函數(shù)運(yùn)行時(shí)所需要的棧空間(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過(guò)函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來(lái)確定。
案例1：
計(jì)算BubbleSort的空間復(fù)雜度？
- 這里的這個(gè)空間復(fù)雜度是多少？—>>
O(N)還是O(1)
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;
}
}
- 我們?cè)谏厦嬲f(shuō)過(guò)
空間復(fù)雜度算的是變量的個(gè)數(shù)，對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)額外占用存儲(chǔ)空間，有沒(méi)有開(kāi)辟臨時(shí)的空間？有！ - 它們都是常數(shù)個(gè)，所以就是
O(1)
下面這種算法是經(jīng)典的
O(N)
案例2：
計(jì)算Fibonacci的空間復(fù)雜度？
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;
}
- 這里我們
malloc了·n+1·個(gè)空間 - 其他的都忽略掉，所以就是O(N)
案例3：
計(jì)算階乘遞歸Fac的空間復(fù)雜度？
long long Fac(size_t N)
{
if (N == 0)
return 1;
return Fac(N - 1) * N;
}
- 這里遞歸空間復(fù)雜度計(jì)算，也是空間累加，但是不同的是空間可以重復(fù)利用
- 所以這里就是
O(N)
6.復(fù)雜度的oj練習(xí)
6.1 消失的數(shù)字
OJ鏈接
- 這里題目要求在時(shí)間復(fù)雜度上
O(n)我們介紹三種方法，看看哪種方法適合這道題~~
方法一：
- 先冒泡排序
- 遍歷，當(dāng)前值+1，不等于下一個(gè)數(shù)
這個(gè)時(shí)間復(fù)雜度是
O(N^2)
方法二：
- 將數(shù)組的每個(gè)元素異或0
- 遍歷，再將異或出來(lái)的結(jié)果每個(gè)再異或
這個(gè)時(shí)間復(fù)雜度是
O(N)
方法三：
- 0到n等差數(shù)列公式計(jì)算和
((首項(xiàng) + 尾項(xiàng)) * 項(xiàng)數(shù))/2 - 依次減掉數(shù)據(jù)中的值，剩下的就是消失的數(shù)字
這個(gè)時(shí)間復(fù)雜度是
O(N)
- 可見(jiàn)只有方法二和方法三符合題目要求，下面我們就寫(xiě)一下這個(gè)代碼
方法二的代碼：
int missingNumber(int* nums, int numsSize){
int N = numsSize;
int sum = ((0+N)*(N+1))/2;
for(int i= 0;i<numsSize;i++){
sum-=nums[i];
}
return sum;
}
方法三的代碼：
int missingNumber(int* nums, int numsSize){
int x = 0;
for(int i = 0;i<numsSize;i++){
x^=nums[i];
}
for(int i = 0;i<=numsSize;i++){
x^=i;
}
return x;
}
6.2 旋轉(zhuǎn)數(shù)組
OJ鏈接
- 我們這個(gè)題肯有些同學(xué)在C語(yǔ)言的時(shí)候做過(guò)
我們先來(lái)看思路一：
- 思路一的時(shí)間復(fù)雜度是多少？
- 可能有的同學(xué)算出來(lái)的是
O(N*K)，不完全正確~~
- 可能有的同學(xué)算出來(lái)的是
- 最好的情況：k % N = 0，k = 7，旋轉(zhuǎn)0次?。?！是
O(1)。k是N的倍數(shù)時(shí)，不需要旋轉(zhuǎn)~~ - 最壞的情況：k % N = N - 1時(shí)，比如13次旋轉(zhuǎn)的最多，20次最多…
- 所以這個(gè)題的真正復(fù)雜度是
O（N*(N-1)）—>O(N^2)
那么我們要求時(shí)間復(fù)雜度是
O(N)，那么我們?cè)趺磧?yōu)化呢？
我們這里就要看思路二：
- 這里很明顯是
O(N)
代碼如下：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-715626.html
void reverse(int* nums,int left,int right){
while(left<right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k){
if(k>numsSize){
k %=numsSize;
}
reverse(nums,0,numsSize-1);
reverse(nums,0,k-1);
reverse(nums,k,numsSize-1);
}
- 注意這里k一定要%numsSize，否則會(huì)報(bào)錯(cuò)~~
思路三：
空間換時(shí)間
- 這里的時(shí)間復(fù)雜是
O(N)，空間復(fù)雜度是O(N)
代碼如下：
void rotate(int* nums, int numsSize, int k) {
k %= numsSize;
int tmp[numsSize];
int j = k;
//拷貝前n-k個(gè)
for (int i = 0; i < numsSize - k; i++) {
tmp[j++] = nums[i];
}
//拷貝后k個(gè)
j = 0;
for (int i = numsSize - k; i < numsSize; i++) {
tmp[j++] = nums[i];
}
//拷貝回原數(shù)組
for (int i = 0; i < numsSize; i++) {
nums[i] = tmp[i];
}
}
好了，數(shù)據(jù)結(jié)構(gòu)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度到這里就結(jié)束了~~
如果有什么問(wèn)題可以私信我或者評(píng)論里交流~~
感謝大家的收看，希望我的文章可以幫助到正在閱讀的你??????文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-715626.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) | 算法的時(shí)間復(fù)雜度和空間復(fù)雜度【詳解】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
