1.2 程序和算法

在现实的世界中，人与人之间的沟通主要是使用语言来进行的。语言是人们创造出来用以表达思想、感情和行为的工具。人类要想和计算机进行交流、要命令计算机来做什么事情同样也是依赖于语言进行的，但是人和计算机之间的沟通与人和人之间的沟通不一样，人类要是想让计算机明白人类想要做什么就必须使用计算机语言（编程语言），然后再借助一定的编译工具编译成计算机能够理解的二进制码，这样才能实现人类与计算机之间的沟通，这些命令或语句的相互组合就是计算机程序，本节将主要对计算机程序和算法进行介绍。

1.2.1 程序

程序是为实现特定目标和目的而用计算机编程语言进行组合的具有一定功能的计算机语言序列。这些计算机语言组成的序列从一定程度上讲表达的是人的思想，即人要通过计算机来实现什么。程序在计算机中运行时根据计算机环境的不同运行效果会有所改变。例如，同样一段代码实现的功能也相同，但是放到不同的计算机上运行的结果虽然一致，但是运行的时间和速度却存在差别。同样，即使这段程序在同一台计算机上运行时也会因为计算机此时的运行效率的不同而使运行速率有所变化，但是不要担心，因为这些现象都是正常的。

计算机程序是用计算机语言来描述的一系列的功能和动作，它实现了开发人员的思想以及要求计算机代替人类要做的事。开发人员在编写计算机程序的时候会因为自身对程序的理解而产生各种各样的区别，编写出来的程序也存在着各种各样的优缺点，因此在实际的学习过程中，懂得了C++中的语法并能够利用C++进行简单代码的开发是远远不够的，它与能够熟练使用C++中的各种功能进行各种简单或复杂软件的开发还存在着很大的差距。学习并使用计算机语言，用它来实现人类想要做的事，并保证它能够在计算机环境下稳定、可靠、高效执行，就要会用计算机程序设计的方法来将计算机语言组成特定的功能序列。学习计算机程序和学习汉语、英语等其他语言一样，要靠平时的积累和练习，只能多读、多练才能更好地理解和运用语言，才能够编写出稳定、高效、健壮的计算机程序。同样，在学习的过程中要养成良好的编程习惯，如规范代码格式、添加代码注释等。

开发人员编写的程序要符合计算机语言的要求规范，因为计算机在运行程序时是按照一定的规范来操作的，只有遵守了计算机语言的开发规范才能保证编写的程序能够顺利运行。因此，开发人员在编写程序的时候一定要按照计算机语言的规范来进行编写，C++程序员也是一样，必须遵守C++语言的编写规范，编译器才能编译通过，计算机才能顺利执行。

1.2.2 算法

许多计算机书中都提到算法是程序的灵魂，算法的设计和开发工作在程序的编写过程中占据着重要的位置。所谓算法就是为解决一系列问题而编写设计的一系列程序语句，是程序语句按照一定的功能用途相互组合的结果。通常一个完整的算法都含有零个或多个输入，然后程序内部对输入数据进行处理和计算，在经过有限的时间后得到一个正确的结果。如果一个算法存在缺陷，则得不到相应正确的结果。一个完整、正确的算法通常具有以下几个特征。

❑ 有穷性：算法在进行了有限次的计算与运行之后必须结束，不能够在程序中无限循环。

❑ 确定性：每一个算法中的每一个步骤都是确定、清楚的，在算法中都有确定的意义，不是模糊的。

❑ 有零个或多个输入：算法的输入可以对算法的初始状态进行初始化，但也可以不对算法的初始状态进行初始化，即初始化时输入个数为0。

❑ 有一个或多个输出：一个算法必须有一个输出，也可以有多个输出。如果一个算法没有任何输出，那么这个算法是完全没有意义的。

❑ 有效性：算法在经过有限次的运行之后会得到一个正确的、确定的结果。算法的每一个步骤必须有效并且能够精确地运行。

每一个算法都有一个衡量其效率的标准，算法的复杂度可以分为时间复杂度和空间复杂度。算法的时间复杂度是指算法运行时需要消耗的时间资源。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做T(n)=O(f(n))。

因此，在计算机算法中问题的规模越大，算法运行时消耗的计算机资源也就越多，算法运行的时间也就越长。下面来详细介绍一下算法时间复杂度的计算方法。

【实例1-1】for循环的时间复杂度。

        #include<iostream>           //头文件
        using namespace std;         //标准命名空间
        #define  N  10               //定义一个宏
        //主函数入口
        int main()
        {
            int  i ;
            int  j ;
            int  k ;
            int  sum = 0 ;
            for(i=0;i<N;i++)
            {
                for(j=0;j<N;j++)
                {
                    for(k=0;k<N;k++)
                    {
                        sum = sum + 1;
                    }
                }
            }
        }

上面代码段的功能是累加1，并将累加结果保存到sum变量中，直到循环结束位置。上面的sum = sum + 1语句被执行了1000次，因此算法作用的时间复杂度为N×N×N。记作：

T(n)=O(n^3)

如果算法不一样，最终可能产生的时间复杂度也不一致。例如，若算法中语句执行次数为一个常数，则时间复杂度为O(1)，另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1的频度不同，但时间复杂度相同，都为O(n^2)。

按数量级递增排列，常见的时间复杂度有：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)，...，k次方阶O(nk)，指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率不断降低。

空间复杂度是指算法在计算机内执行时所需要的存储空间的大小，空间复杂度与时间复杂度类似，记作S(n)=O(f(n))。

算法的空间复杂度通常由以下三个方面给出。

❑ 算法本身的长度：算法本身存在着一定的长度，因此算法自身的存储空间与算法的自身大小成正比例关系，算法越长，占用的存储空间越多，因此在实际的编写过程中要尽量编写出程序较短的算法。

❑ 算法的输入与输出：算法的输入与输出是由算法解决的问题来决定的，算法开始时需要传入的参数越多占用的空间也就越多，反之占用的空间也就越少。

❑ 算法运行时所占用的临时空间的大小：算法运行时所占用的临时空间的大小随着算法的不同而不同，有的算法在运行过程中占用的临时空间的大小是固定不变的，也不随问题规模的大小改变而改变，这种算法就节省了算法的空间复杂度，有的算法在运行过程中所占用的临时存储空间是不断改变的，并随着问题规模的大小而变化。问题规模越大，占用的存储空间也就越多。

在分析一个算法的空间复杂度时要从各个方面进行考虑。例如，在递归算法中，算法自身的长度可能比较短，自身占用的存储空间比较小，但是运行时所占用的临时存储空间可能会随着递归的运行而不断增加。在非递归算法中，算法自身的长度可能会比较长，算法自身占用的存储空间比较大，但是在运行时，占用的临时存储空间可能会比较小。

在实际的算法设计和开发过程中，对算法的时间复杂度和空间复杂度要综合进行考虑，不能只偏向一个方面而忽略了整体的效率。对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。时间复杂度满足要求时，空间复杂度的性能可能变得很差，即可能会占用较多的存储空间；反之，当空间复杂度获得良好的效果时，时间复杂度的性能可能会变得很差，即可能会占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法（特别是大型算法）时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性、算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。