2018 December 14 数据结构, 算法

聊聊数据结构与算法：基础知识

前言

Pascal之父Nicklaus Wirth说过：“算法+数据结构=程序”，数据结构与算法的重要性不用多说，几乎每个计算机科学专业的学生或者学习编程的程序员都必须要学的一门理论课程。但是学习难度是比较高的，尤其是算法，难先不说，实际工作中也用的不多，现在写一个程序往往有许多的框架和库可以直接使用，完全不用关心算法是如何实现的，学习算法的回报和成就感都没有学习一个MVC框架来得快。

但是这并不意味着数据结构与算法没有用处，如果停留在“使用”的层面只能解决已知问题，对于未遇到过的问题就无法变通应对，同时，学习这类的计算机科学理论知识，除了可以了解到底层的运作原理以外，还可以学到很多巧妙的解题思路，这些思路无论是在系统底层还是上层，小型单体应用还是大型分布式应用，都能看得到它们的存在。

算法复杂度

算法复杂度分为时间复杂度和空间复杂度。

时间复杂度是指执行算法所需要的计算工作量
空间复杂度是指执行这个算法所需要的内存空间

算法的时间复杂度是一个函数，它定性描述了该算法的运行时间，经常用来体现算法的速度有多快。

大O表示法

我们通常用大O表示法来表示算法的时间复杂度。大O阶的推导方法如下：

用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常数阶

int sum = 0, n = 100; /* 执行一次 */
sum = (1+n)*n/2;      /* 执行一次 */
printf("%d", sum);    /* 执行一次 */

这段代码的运行次数函数是f(n)=3，根据大O阶的推导方法，第一步把常数项3改为1，但是之后在保留最高阶项时发现没有最高阶项，所以这段代码的时间复杂度为O(1)。

线性阶

int i;
for (i = 0; i < n; i++)
{
    /* 时间复杂度为O(1)的程序步骤序列 */
}

这段代码的运行次数函数是f(n)=n，因为循环体中的代码需要执行n次，没有常数项也没有最高阶项，所以这段代码的时间复杂度为O(n)。

对数阶

int count = 1;
while (count < n)
{
    count = count * 2;
    /* 时间复杂度为O(1)的程序步骤序列 */
}

这段代码每次都让count乘以2，直到count大于等于n，换句话说，就是2的x次方可以大于等于n，即n=2^x，得到运行次数函数是f(n)=log2(n)，由于对数的底数2对整体复杂度影响不大可以忽略，所以这段代码的时间复杂度为O(log(n))。

平方阶

int i,j;
for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

这段代码是一个循环嵌套，所以很明显这段代码的时间复杂度为O(n^2)。

再看一个稍微复杂一点的例子：

n++;                    /* 执行次数为1 */
function(n);            /* 执行次数为n */
int i,j;
for (i = 0; i < n; i++) /* 执行次数为n^2 */
{
    function(i);
}
for (i = 0; i < n; i++) /* 执行次数为n(n+1)/2 */
{
    for (j = i; j < n; j++)
    {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}