如何计算算法的时空复杂度

算法：

时间复杂度：

原文地址：http://blog.csdn.net/com_ice/article/details/79025117

时空复杂度：

https://www.cnblogs.com/zakers/archive/2015/09/14/4808821.html

时间复杂度O(logn):

O(logn)的出现，一般是采用了分治的思想，算法体现就是递归。logn的底数由算法的复杂度决定：二分法，底数为2；三分法，底数是3...

但是我们把log_xn,，log_yn，x!=y，n取正无穷大时，会发现其实不同底数的logn只相差一个常数，因此我们在算法里面极端的认为：log_xn = log_yn。因此我们在说l算法为logn时并不带底数。

有一个常识：一个优秀的程序员在发现自己的算法时间复杂度为O(n²)时，立即会想到能否改进到O(logn)，一个原因是O(logn)比O(n²)要快很多；二是一般情况下是可以优化的（不绝对，不要钻牛角尖）。

附一个递归求最大子项和的算法以供理解：

#include <stdio.h>
int main()
{
    int a[]={2,-3,9,2,-4,-1,9,3,-3,1,4,-6};    
    int N=sizeof(a)/sizeof(int);    
    int maxValue=MaxSubsequnce3(a,0,N-1);
    printf("%d %d %d",maxValue,begin,end);
    return 0;
}

//分治思想：递归算法，时间复杂度：O(nlogn) 
int MaxSubsequnce3(int a[], int Left, int Right)  
{  
    if (Left == Right)    /* 递归的基准情形 */  
        return a[Left];  
  
    int Center,i;  
    Center = (Left + Right) / 2;   /* 求分界点 */  
    int MaxLeftSum;  
    MaxLeftSum = MaxSubsequnce3(a, Left, Center);   /* 递归，求左半部分子序列的最大子序列和 */  
    int MaxRightSum;  
    MaxRightSum = MaxSubsequnce3(a, Center + 1, Right);  /* 递归，求右半部分子序列的最大子序列和 */  
  
    /* 求横跨左半部分和右半部分的最大子序列和 */  
    /* 首先是左半部分子序列中包含最后一个元素的最大子序列和 */  
    int MaxLeftBorderSum = a[Center], LeftBorderSum = a[Center];  
    for (i = Center - 1; i >= Left; --i) {  
        LeftBorderSum += a[i];  
        if (LeftBorderSum > MaxLeftBorderSum)  
            MaxLeftBorderSum = LeftBorderSum;  
    }  
  
    /* 接着是右半部分子序列中包含第一个元素的最大子序列和 */  
    int MaxRightBorderSum = a[Center + 1], RightBorderSum = a[Center + 1];  
    for (i = Center + 2; i <= Right; ++i) {  
        RightBorderSum += a[i];  
        if (RightBorderSum > MaxRightBorderSum)  
            MaxRightBorderSum = RightBorderSum;  
    }  
  
    /* Max3 返回左、右半部分子序列的最大子序列和以及横跨左、右半部分的最大子序列和中的最大者 */  
    int theLeftRight= MaxLeftBorderSum + MaxRightBorderSum, max;
    max= MaxLeftSum> MaxRightSum? MaxLeftSum: MaxRightSum;
    max= max> theLeftRight? max: theLeftRight;
    return max;
}

View Code

这道题最差算法需要O(n³)，递归使其降为O(logn)，但最优算法可以是O(n)→在线处理算法，了解一下~

这里讲得更详细：https://blog.csdn.net/jdbc/article/details/42173751