本文共 1344 字，大约阅读时间需要 4 分钟。

2.1 算法的定义

算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

2.2 算法的特性

算法的五个特性：输入、输出、有穷性、确定性和可行性。

输入和输出：算法具有零个或多个输入，至少有一个或多个输出。

有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且一个步骤在可接受的时间内完成。

确定性：每一步骤都有确定含义，没有二义性。

可行性：算法每一步都是必须可行的。每一步都能通过执行有限次数完成。

2.3 算法设计的要求

正确性：指算法至少具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够的到问题的正确答案。

可读性：方便阅读、理解和交流

健壮性：输入的数据不合法时，能够做出相关处理，而不会产生异常或莫名其妙的结果。

时间效率高和存储量低。

2.4 算法效率的度量方法

2.4.1 事后统计方法

事后统计方法：采用的是提前设计好测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，然后确定效率高低。

缺陷：①提前编好程序，花费大量时间和精力。

           ②可能会掩盖算法本身的优劣。

           ③测试的数据设计困难。

2.4.2 事前分析估计法

事前分析估计法：在计算机程序编制前，提前进行估算。

取决因素：①算法采用的策略、方法

                  ②编译产生的代码质量

                  ③问题的输入规模。

                  ④机器执行指令的速度。

算法运行时间=一个简单操作所需的时间×简单操作次数（语句频度）

注：但是一个简单操作所需的时间一般随机器而异的。

 我们把算法所耗费的时间定义为该算法中每条语句的频度之和，则上述算法的时间消耗T(n）为：

                                            T（n）=2n^3+3n^2+2n+1

2.5 函数的渐近增长

 

函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得所有的n>N,f(n)总是比g(n)大，那么f(n)的增长渐近快于g(n)。

 n=1时，算法A效率比如B，n=2时，两者效率相等，n>2时，算法A好于B。随着n的增加，A比B越来越好（执行次数比B少），所以最后算法A总体上是好于B的.

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，应关注主项（最高阶项）的阶数。

2.6 算法时间复杂度

2.6.1 算法时间复杂度的定义

定义：算法的时间复杂度，也就是算法的时间量度，记作T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。

一般随着n的增大，T(n)增长最慢的算法称为最优算法。

2.6.2如何分析算法时间复杂度

推导大O阶：①用常数1取代运行时间中的所有加法常数

                     ②在修改后的运行次数函数中，只保留最高阶项

                     ③如果最高阶项存在且其系数不是1，则去除与这个项相乘的系数，得到的结果就是大O阶。

 例题：

注意：不管这个常数是多少，时间复杂度都为O(1),而不是O(3),

 若循环执行1次:count=1*2=2； 若循环执行2次:count=2*2=2^2； 若循环执行3次:count=2*2*2=2^3;若循环x次：count=2^x。

设语句2执行次数为x次，由循环条件count<n,所以2^x=n;得x=,所以O().

2.7 常见的时间复杂度

转载地址：http://rbsduy.baihongyu.com/