時(shí)間復(fù)雜度和空間復(fù)雜度+劍指offer習(xí)題

• 時(shí)間復(fù)雜度介紹
• • 大O的漸進(jìn)表示法
  • 有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：
• 實(shí)例
• • 實(shí)例一（循環(huán)）
  • 實(shí)例二（嵌套循環(huán)）
  • 實(shí)例三（冒泡排序）
  • 實(shí)例四（二分法）
  • 實(shí)例五（階乘遞歸）
  • 實(shí)例六(斐波那契數(shù)列)
• 空間復(fù)雜度介紹
• 兩者的關(guān)系比較
• 實(shí)例
• • 實(shí)例一（冒泡排序）
  • 實(shí)例二(階乘)``
• 劍指offer
• • 消失的數(shù)字
  • 輪轉(zhuǎn)數(shù)組問題
  • 字符串旋轉(zhuǎn)問題（補(bǔ)充）

成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),和碩企業(yè)網(wǎng)站建設(shè),和碩品牌網(wǎng)站建設(shè),網(wǎng)站定制,和碩網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,和碩網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。時(shí)間復(fù)雜度介紹

程序運(yùn)行的時(shí)候會(huì)消耗時(shí)間資源和空間（內(nèi)存）資源，因此衡量一個(gè)算法的好壞，可以從時(shí)間復(fù)雜度和空間復(fù)雜度來看。
時(shí)間復(fù)雜度： 算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量的描述了算法的運(yùn)行時(shí)間。算法中基本操作的執(zhí)行次數(shù)為算法的時(shí)間復(fù)雜度。我們一般不需要精確的知道一個(gè)程序的執(zhí)行次數(shù)，也只需要大概估計(jì)出次數(shù)，這里我們一般用大O的漸進(jìn)表示法

大O的漸進(jìn)表示法

首先大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。
1、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
例如：執(zhí)行常數(shù)次（1,100或者1000），表示為O(1)
2、在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
例如： 執(zhí)行(N^2 +N)次， 表示為O(N^2)
3、如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)，得到的便是大O的漸進(jìn)表示法
例如： 執(zhí)行 (N*(N+1)/2）次， 表示為O（N^2）

有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：

最壞情況：任意輸入規(guī)模的大運(yùn)行次數(shù)(上界)
平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)

例如：在一個(gè)長度為N數(shù)組中搜索一個(gè)數(shù)據(jù)x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到

在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況，所以數(shù)組中搜索數(shù)據(jù)時(shí)間復(fù)雜度為O(N)。

實(shí)例 實(shí)例一（循環(huán)）

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);
}

兩個(gè)for循環(huán)， 一個(gè)循環(huán)執(zhí)行M次，另一個(gè)執(zhí)行N次，
所以精確的次數(shù)就為：（M+N）
大O的漸進(jìn)表示法
由于M和N都是未知數(shù)，
第一種：如果沒有說明M和N的大小關(guān)系，O(M+N)
第二種：如果M >>N，O(M)
第三種：如果M<<, O(N)
第四種：如果M和N差不多大小， O(M) 或者O(N)

實(shí)例二（嵌套循環(huá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);
},

一個(gè)for循環(huán)的嵌套,執(zhí)行次數(shù)N^2,后面一個(gè)for,2N次，后面一個(gè)while,執(zhí)行次數(shù)10次。
精確次數(shù)：N^2+2N+10
大O漸進(jìn)表示法：O(N^2)

實(shí)例三（冒泡排序）

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 - 1次，第二趟比較N - 2 次， 第三趟比較 N - 3次，…一直到第N - 1趟， 比較1次。
所以執(zhí)行的精確次數(shù) = N - 1 + N - 2+ N - 3+ N - 4+ N - 5+ ……1(就是個(gè)等差數(shù)列求和) =N(N - 1)/2*
大O的漸進(jìn)表示法：N^2

實(shí)例四（二分法）

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);
 if (a[mid]< x)
 begin = mid+1;
 else if (a[mid] >x)
 end = mid;
 else
 return mid;
}
return -1;
}

首先，我們必須要明白算時(shí)間復(fù)雜度，我們不能去看它是幾層循環(huán)，而是要去看它的思想。
二分法：是從左邊和右邊，向中間找，最好的情況：自然是一次就找到了，但是時(shí)間復(fù)雜度，是要考慮最壞的情況，第一沒找到的話，便會(huì)在左邊一半中找，或者是在右邊的一半中尋找，就這樣一直找，直到找到為止，所以每找一次，便是2（可以想象折紙反過來展開的過程）。
最好的情況：O(1)
最壞的情況(一般考慮最壞的情況)：如果查找次數(shù)為x次，找一次就是2， 12222 … = N
–>2^x = N —>x = log2(2為底)N -->O(log以2為底N的對(duì)數(shù))

實(shí)例五（階乘遞歸）

long long Factorial(size_t N)
{return N< 2 ? N : Factorial(N-1)*N;
}

遞歸了N次，所以時(shí)間復(fù)雜度為：O(N)

實(shí)例六(斐波那契數(shù)列)

long long Fibonacci(size_t N)
{return N< 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

遞歸的算法 = 遞歸的次數(shù)*每次遞歸調(diào)用的次數(shù)
這里每次遞歸調(diào)用的次數(shù)為0(1), 所以就算遞歸次數(shù)就行了

有圖可以看到，次數(shù)= 2^0 + 2^1 + 2^2 + 2^3 …+ 2^n-1 - x(因?yàn)橛蓤D，越往后Fib()中的值越小， 而右邊Fib()中的值比左邊的小，右邊Fib()中個(gè)的值肯定先被減為0，所以就要減去x ,這多算的部分)
—>x太小可以忽略不計(jì)， ---->2^n - 1 - x - 1
由于1和x遠(yuǎn)小于 2^n - 1,所以忽略不計(jì)
則：O(2^N)

空間復(fù)雜度介紹

空間復(fù)雜度：空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度，我們也是使用大O的漸進(jìn)表示法。

兩者的關(guān)系比較

時(shí)間一去不復(fù)返的，空間是可以重復(fù)利用的，空間復(fù)雜度算的是臨時(shí)占用內(nèi)存（額外的）

實(shí)例 實(shí)例一（冒泡排序）

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;
}
}

使用了常數(shù)個(gè)空間，被反復(fù)利用，
空間復(fù)雜度:O(1)

實(shí)例二(階乘)``

long long Factorial(size_t N)
{return N< 2 ? N : Factorial(N-1)*N;
}

3遞歸調(diào)用了N次，開辟了N個(gè)棧幀，每個(gè)棧幀使用了常數(shù)個(gè)空間。空間復(fù)雜度為O(N)

劍指offer 消失的數(shù)字

鏈接：消失的數(shù)字OJ鏈接

題目要求是在O(n)的時(shí)間內(nèi)完成，這里我們可以看到，對(duì)時(shí)間提出了要求。
算法一：用完整的數(shù)組減去殘缺的數(shù)組 = 得到缺失的數(shù)字
即------>(0 + 1 +2 +3 + 4 +5 + 6 + …n) - (a[0] + a[1] + a[2] + a[3] + a[4] +…+ a[n])
算法一：空間復(fù)雜度為O(1), 時(shí)間復(fù)雜度為O(n)

算法二：運(yùn)用異或的思想
異或（^）: 兩個(gè)相同數(shù)異或，結(jié)果為0
0與任何數(shù)異或，結(jié)果為任何數(shù)
1與任何數(shù)異或， 都為1

第一步，設(shè)x = 0，讓x與 [0, n] 這個(gè)區(qū)間的所有數(shù)異或，
------>0 ^ 0 ^ 1^ 2 ^ 3^ 4^ 5^6 ^…n
第二步，再讓x 與數(shù)組中的每個(gè)值異或，
------>0 ^ 0 ^ 1^ 2 ^ 3^ 4 ^ 5^6 ^…n ^ 0 ^ 1^ 2 ^ 3^ 4^ 5^6 ^…n - 1
(相同的，出現(xiàn)2次的便異或消掉了，剩下的就是出現(xiàn)一次的)
-------->0 ^ 缺失的數(shù)字 = 缺失的數(shù)字
最后， x = 缺失的數(shù)字
算法二：空間復(fù)雜度O(1), 時(shí)間復(fù)雜度O(n)

算法一很簡單，這里，我來介紹算法二。

int missingNumber(int* nums, int numsSize)
{int x = 0;

    for(int i = 0; i<= numsSize; i++) // x與[0, n]異或
    {x ^= i;
    }

    for(int i = 0; i< numsSize; i++)  // x在與數(shù)組上的每個(gè)數(shù)異或，出現(xiàn)2次的為0
    {x ^= nums[i];
    }

    return x;
}

輪轉(zhuǎn)數(shù)組問題

鏈接： 輪轉(zhuǎn)數(shù)組OJ鏈接


思路一：暴力求解，旋轉(zhuǎn)k次
時(shí)間復(fù)雜度O(N*k), 空間復(fù)雜度O(N)

思路二：開辟一個(gè)空間，用另一個(gè)數(shù)組

如圖，讓nums這個(gè)數(shù)組旋轉(zhuǎn)3次， 創(chuàng)建一個(gè)tmp的數(shù)組，
第一步：讓nums后三個(gè)數(shù)，拷貝到tmp這個(gè)數(shù)組中去
第二步：再讓前面的數(shù)，拷貝到tmp這個(gè)數(shù)組中去，
這樣就實(shí)現(xiàn)了，nums這個(gè)數(shù)組向右旋轉(zhuǎn)3次
時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度： O(N)

思路三：****（最優(yōu)解）

這種算法，時(shí)間復(fù)雜度O(N), 空間復(fù)雜度O(1)
下面我來重點(diǎn)介紹這種算法，
由圖可知，數(shù)組的個(gè)數(shù)為n，旋轉(zhuǎn)的次數(shù)為k
第一步：先n - k個(gè)逆置
第二步：后面k個(gè)逆置
第三步：整體逆置
結(jié)果便是旋轉(zhuǎn)之后的數(shù)組
**注意：**當(dāng) n = k時(shí)候，
第一步就是先0個(gè)逆置，第一步就不旋轉(zhuǎn)
第二步，后面k個(gè)逆置，相當(dāng)于整體逆置
第三步，再整體逆置
結(jié)果就是沒有旋轉(zhuǎn)，

即 n = k時(shí)，不用旋轉(zhuǎn)
基于這個(gè)，我們可以優(yōu)化下計(jì)算
如果 k = n + 3,那么就相當(dāng)于只旋轉(zhuǎn)3次（因?yàn)閚 = k相當(dāng)于不旋轉(zhuǎn)）
下面是思路三的代碼

void verse(int* nums, int left, int right) //先寫一個(gè)逆置的函數(shù)
{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;
    }

    verse(nums, 0, numsSize - k- 1); //前n - k的逆置，不太清楚下標(biāo)的，可以舉個(gè)例子 
    verse (nums, numsSize - k, numsSize - 1 ); // 后 k 個(gè)逆置
    verse(nums, 0, numsSize - 1);            // 整體逆置
}

字符串旋轉(zhuǎn)問題（補(bǔ)充）

題目： 判斷一個(gè)字符串，是否為另一個(gè)字符串旋轉(zhuǎn)而來的 。
例如 abcded 向左旋轉(zhuǎn)2個(gè) 為 cdedab

思路一：就是寫一個(gè)字符串，然后再把它旋轉(zhuǎn)的每種情況寫出來，從而進(jìn)行判斷
這種方法肯定過于麻煩。

思路二**(優(yōu)解)**：如果你對(duì)字符串函數(shù)比較了解，那么可以直接用字符串函數(shù)來做
首先，假設(shè)初始字符串?dāng)?shù)組str1, 有另一個(gè)字符串?dāng)?shù)組 str2， 判斷str2是否有由str1 旋轉(zhuǎn)而來的

第一步，使用strncat函數(shù)，將strncat(str1, str2, strlen(str2)); ---->將字符串?dāng)?shù)組str2追加到str1上去。(不使用strcat函數(shù)， 原因是這個(gè)函數(shù)不能夠追加自己本身，這樣的話，就忽略了, str1與str2 相等的情況 即旋轉(zhuǎn)的次數(shù)為 這個(gè)字符串?dāng)?shù)組大小的整數(shù)倍)

第二步，使用strstr函數(shù)， strstr(str1, str2);判斷str2是否為str1的子集
最后，如果是子集 那么str2肯定就是由str1旋轉(zhuǎn)得來的

當(dāng)然，這個(gè)算法我們也可以有個(gè)優(yōu)化，
如果str1與str2字符串長度不相等，那么么str2肯定就不是由str1旋轉(zhuǎn)得來的。
代碼如下：

溫馨提示：，被追加的那個(gè)字符串?dāng)?shù)組大小，一定要大于等于兩個(gè)字符串?dāng)?shù)組之和，不然會(huì)造成越界訪問

#define _CRT_SECURE_NO_WARNINGS 1
#include#includeint deduce(char* str1, char* str2)
{int first = strlen(str1);
    int second = strlen(str2);

    if (first != second)
    {return 0;
    }

    strncat(str1, str1, first);
    
    char* re = strstr(str1, str2);
    if (re == NULL)
    {return 0;
    }
    else
    {return 1;
    }
}   

int main()
{ char arr1[30] = {"abcde" };
     char arr2[24] = {"deabc" };

    int ret = deduce(arr1, arr2);

    if (ret == 0)
    {printf("NO");
    }
    else
    {printf("YES");
    }

    return 0;
}

更新不易，麻煩多多點(diǎn)贊，歡迎你的提問，感謝你的轉(zhuǎn)發(fā)，最后的最后，關(guān)注我，關(guān)注我，關(guān)注我，你會(huì)看到更多有趣的博客哦！！！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁標(biāo)題：時(shí)間復(fù)雜度和空間復(fù)雜度+劍指offer習(xí)題-創(chuàng)新互聯(lián)
文章源于：http://m.newbst.com/article42/dcgchc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、外貿(mào)建站、定制網(wǎng)站、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)