C語言關於時間復雜度詳解

一、時間復雜度

1.什麼是時間復雜度?

空間效率,時間效率(較為關註)

時間復雜度:算法中的操作執行次數,為算法的時間復雜度。(不是具體時間,而是執行次數

2.如何計算?

時間復雜度

(1)是一個估算,看表達式中影響大的那一項,如N*N+2N+10中,N*N對整個式子影響最大,故其時間復雜度為N*N,用大O的漸近表示法O(N*N)。

(2)去掉時間表達式中的常數項乘積,例如,得到一個準確的時間表達式為2N+10,則估算得到的時間復雜度為O(N)

(3)對於多個未知數時,例如時間表達式為N+M,假設M,N差不多大,則O(M)或O(N);假設M遠大於N,則O(M)。

(4)用常數1去替代所有確定的常數,如準確的時間表達式為100,O(1).

(5)未知數和常數,濾去常數。

(6)另外有些算法分為最好,最壞,平均這三種情況。當算法存在這三種情況時,選最壞的時間復雜度,例如假設字符串長度為N,“sdsfrsgtr…”,遍歷字符串,求S的時間復雜度,最好O(1),最壞O(N),平均O(N/2)。

A.  在冒泡排序中,

     第一趟冒泡:N

     第二趟冒泡:N-1

     第三趟冒泡:N-2

     第N趟冒泡:1

     為等差數列,準確次數為:        N*(N+1)/2

冒泡排序時間復雜度為O(N*N)

B.  在二分查找/折半查找中:

假設二分瞭X次,有1*2*2….*2=N,2^X=N, X=(log2) N

算法的復雜度計算中,喜歡省略成logN,因為不好寫底數,但是寫成lg N,是錯的。

C.  在某些階乘的運算中求時間復雜度:

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

如Factorial(10),則返回factorial(9)*10,在返回到factorial(9)*8…..以此類推返回到

factorial(1)*2返回到1.(實際是10!)遞歸瞭N次,故時間復雜度為O(N)。(特別註意:結返回結果是N!,但是操作的次數是遞歸瞭N次,所以時間復雜度為O(N))

3.常見的時間復雜度:

查看源圖像

 二、空間復雜度

1.什麼是空間復雜度?

空間復雜度是算法運行過程中臨時占用存儲空間大小的量度,不在意其具體占瞭多少比特的大小,而是計算變量的個數。

2.如何計算?

對照時間復雜度的計算方法。註意:時間是累積的,空間是不累計的,空間可以銷毀。

例題1:消失的數字

思路1:排序 0 1 2 3 4 5 6 7 9 一次比較,若下一個數與上一個數隻差為1,則掠過,若下一個數比上一個數>1,則找到,但時間復雜度不符合。

思路2:把0到N加到一起,結果ret1,再把數組中的數加到一起ret2,ret1-ret2就是要找的數。

思路3:異或:相同為0,相異為1。將數組中的數與0-N數互相異或,最後剩下的那個數字就是缺的那個數。

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

要註意0-N數異或時,註意j<numsSize+1,它比原數組中元素個數多1。

 例題2:旋轉數組

思路1:保存最後一個數,將其挪到前面來。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;
    }
}

但此時時間復雜度為O(N*K),跑不過~

思路2:以空間換時間,嘗試著多消耗一點空間,一次換成。將後K個保存,移到前面來,直接得到。時間復雜度為O(N),空間復雜度為O(N)

思路3:後K個逆置,前K個逆置,整體逆置(這個實在是太牛瞭!!)

 

 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)
{
    //控制好下標,後N-K個
    Reverse(nums,numsSize-k,numsSize-1);
    Reverse(nums,0,numsSize-k-1);
    Reverse(nums,0,numsSize-1);
 
}

 註意結果可能出錯:

 此時需要註意K是否大於N,當K>N時需要取模: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;
    }
    //控制好下標,後N-K個
    Reverse(nums,numsSize-k,numsSize-1);
    Reverse(nums,0,numsSize-k-1);
    Reverse(nums,0,numsSize-1);
 
}

在力扣上運行得到:

總結

到此這篇關於C語言關於時間復雜度詳解的文章就介紹到這瞭,更多相關C語言時間復雜度內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: