数据结构(一)时间复杂度

数据结构...本系列旨在对基础算法进行记录和学习,为了之后的面试一个弥补~~

本系列不是科普文,如果完全小白得百度看一下类似说明文.

1.算法的效率

虽然计算机能快速的完成运算处理，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到算法的效率。

算法的效率主要由以下两个复杂度来评估：
时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

设计算法时，一般是要先考虑系统环境，然后权衡时间复杂度和空间复杂度，选取一个平衡点。不过，时间复杂度要比空间复杂度更容易产生问题，因此算法研究的主要也是时间复杂度，不特别说明的情况下，复杂度就是指时间复杂度。

本文主要说明时间复杂度,空间复杂度一笔带过...

2.空间复杂度

使用递归很容易造成空间爆炸,下面就是一个典型的例子,不过一般的写算法很少去考虑这个问题

写深度学习考虑的比较多,这里就先不去考虑

空间复杂度

3.时间复杂度

本文主要说明大O时间复杂度,其它基本不用也没必要学~

基础不去说明,下面直接给例子:

问题说明

第一种方法:

//T(N) = O(N^3)
int MaxSubseqSum1(int A[],int N)
{
    int ThisSum,MaxSum=0;
    int i,j,k;
    for(i = 0;i<N;i++)
    {
        for(j=i;j<N;j++)
        {
            ThisSum = 0;
            for(k=i;k<=j;k++)
                ThisSum += A[k];
            if(ThisSum>MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}

第二种方法:

//T(N) = O(N^2)
int MaxSubseqSum2( int A[], int N )
{
    int ThisSum, MaxSum = 0;
    int i, j;
    for( i = 0; i < N; i++ )
    {
        ThisSum = 0;
        for( j = i; j < N; j++ )
        {
            ThisSum += A[j];
            if( ThisSum > MaxSum )
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}

第三种方法:

第三种方法

第四种方法:

第四种方法

举这个例子可以把时间复杂度概念完全理清楚,而且还可以发散我们的思维

当遇到一个算法复杂度是T(N) = O(N^2),那么我们就想办法把算法提高到O(NlogN )

复杂度时间表

按照上面这个时间表,我们就可以对算法进行改进,当然初学者还是先写出来再说吧~~

参考:

浙江大学数据结构

网上大神博客