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

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

空間效率，時(shí)間效率（較為關(guān)注）

時(shí)間復(fù)雜度：算法中的操作執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。（不是具體時(shí)間，而是執(zhí)行次數(shù)）

2.如何計(jì)算？

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

（1）是一個(gè)估算，看表達(dá)式中影響大的那一項(xiàng)，如N*N+2N+10中，N*N對(duì)整個(gè)式子影響最大，故其時(shí)間復(fù)雜度為N*N，用大O的漸近表示法O（N*N）。

（2）去掉時(shí)間表達(dá)式中的常數(shù)項(xiàng)乘積，例如，得到一個(gè)準(zhǔn)確的時(shí)間表達(dá)式為2N+10，則估算得到的時(shí)間復(fù)雜度為O（N）

（3）對(duì)于多個(gè)未知數(shù)時(shí)，例如時(shí)間表達(dá)式為N+M，假設(shè)M，N差不多大，則O（M）或O（N）；假設(shè)M遠(yuǎn)大于N，則O（M）。

（4）用常數(shù)1去替代所有確定的常數(shù)，如準(zhǔn)確的時(shí)間表達(dá)式為100，O（1）.

（5）未知數(shù)和常數(shù)，濾去常數(shù)。

（6）另外有些算法分為最好，最壞，平均這三種情況。當(dāng)算法存在這三種情況時(shí)，選最壞的時(shí)間復(fù)雜度，例如假設(shè)字符串長(zhǎng)度為N，“sdsfrsgtr...”,遍歷字符串，求S的時(shí)間復(fù)雜度，最好O（1），最壞O（N），平均O（N/2）。

A.? 在冒泡排序中，

? ? ?第一趟冒泡：N

? ? ?第二趟冒泡：N-1

? ? ?第三趟冒泡：N-2

? ? ?第N趟冒泡：1

? ? ?為等差數(shù)列，準(zhǔn)確次數(shù)為：? ? ? ? N*(N+1)/2

故冒泡排序時(shí)間復(fù)雜度為O（N*N）

B.? 在二分查找/折半查找中：

假設(shè)二分了X次，有1*2*2....*2=N，2^X=N, X=(log2) N

算法的復(fù)雜度計(jì)算中，喜歡省略成logN，因?yàn)椴缓脤?xiě)底數(shù)，但是寫(xiě)成lg N,是錯(cuò)的。

C.? 在某些階乘的運(yùn)算中求時(shí)間復(fù)雜度：

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

如Factorial(10),則返回factorial（9）*10,在返回到factorial（9）*8.....以此類(lèi)推返回到

factorial（1）*2返回到1.（實(shí)際是10！）遞歸了N次，故時(shí)間復(fù)雜度為O（N）。（特別注意：結(jié)返回結(jié)果是N！，但是操作的次數(shù)是遞歸了N次，所以時(shí)間復(fù)雜度為O（N））

3.常見(jiàn)的時(shí)間復(fù)雜度：

?二、空間復(fù)雜度

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

空間復(fù)雜度是算法運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，不在意其具體占了多少比特的大小，而是計(jì)算變量的個(gè)數(shù)。

2.如何計(jì)算？

對(duì)照時(shí)間復(fù)雜度的計(jì)算方法。注意：時(shí)間是累積的，空間是不累計(jì)的，空間可以銷(xiāo)毀。

例題1：消失的數(shù)字

思路1：排序 0 1 2 3 4 5 6 7 9 一次比較，若下一個(gè)數(shù)與上一個(gè)數(shù)只差為1，則掠過(guò)，若下一個(gè)數(shù)比上一個(gè)數(shù)>1，則找到，但時(shí)間復(fù)雜度不符合。

思路2：把0到N加到一起，結(jié)果ret1,再把數(shù)組中的數(shù)加到一起ret2，ret1-ret2就是要找的數(shù)。

思路3：異或：相同為0，相異為1。將數(shù)組中的數(shù)與0-N數(shù)互相異或，最后剩下的那個(gè)數(shù)字就是缺的那個(gè)數(shù)。

int missingNumber(int* nums, int numsSize){
    int x=0;
    //先和數(shù)組的數(shù)進(jìn)行異或
    for(int i=0;i<numsSize;++i)
    {
        x^=nums[i];
    }
    //在和0-N的數(shù)進(jìn)行異或
    for(int j=0;j<numsSize+1;++j)
    {
        x^=j;
    }
return x;
}

要注意0-N數(shù)異或時(shí)，注意j<numsSize+1，它比原數(shù)組中元素個(gè)數(shù)多1。

?例題2：旋轉(zhuǎn)數(shù)組

思路1：保存最后一個(gè)數(shù)，將其挪到前面來(lái)。k次

void rotate(int* nums, int numsSize, int k){
    for(int i=0;i<k;++i)
    {
    int tmp=nums[numsSize -1];
    for(int end=numsSize -2;end >=0;--end)
    {
        nums[end+1]=nums[end];
    }
    nums[0]=tmp;
    }
}

但此時(shí)時(shí)間復(fù)雜度為O（N*K），跑不過(guò)~

思路2：以空間換時(shí)間，嘗試著多消耗一點(diǎn)空間，一次換成。將后K個(gè)保存，移到前面來(lái)，直接得到。時(shí)間復(fù)雜度為O（N），空間復(fù)雜度為O（N）

思路3：后K個(gè)逆置，前K個(gè)逆置，整體逆置（這個(gè)實(shí)在是太牛了！！）

?

?c代碼為：

//逆置
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)
{
    //控制好下標(biāo),后N-K個(gè)
    Reverse(nums,numsSize-k,numsSize-1);
    Reverse(nums,0,numsSize-k-1);
    Reverse(nums,0,numsSize-1);
 
}

?注意結(jié)果可能出錯(cuò)：

?此時(shí)需要注意K是否大于N，當(dāng)K>N時(shí)需要取模：k%=numsSize

添加：if（K>numsSize）{ K%numsSize;}

//逆置
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;
    }
    //控制好下標(biāo),后N-K個(gè)
    Reverse(nums,numsSize-k,numsSize-1);
    Reverse(nums,0,numsSize-k-1);
    Reverse(nums,0,numsSize-1);
 
}

在力扣上運(yùn)行得到：

總結(jié)