> 一次数学课上，老师让学生练习算数。于是让他们一个小时内算出1+2+3+4+5+6+……+100的得数。全班只有高斯用了不到20分钟给出了答案，因为他想到了用（1+100）+（2+99）+（3+98）……+（50+51）…………一共有50个101，所以50×101就是1加到一百的得数。后来人们把这种简便算法称作高斯算法。 ### 算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 ### 算法的描述： 自然语言 流程图 程序设计语言 伪码 ### 算法的特性： - 输入:有0个或多个输入 - 输出 : 有一个或多个输出（处理结果） - 有穷性 : 算法应在执行有穷步后结束 - 确定性 : 每步定义都是确切、无歧义的 - 可行性 :算法中所有的操作都必须可以通过已经实现的基本操作执行有限次来实现。 ### 算法的评价 - 正确性 - 可读性 - 健壮性 - 高效性（时间代价和空间代价） ### 算法的效率的度量 算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量 *事后统计 *事前分析估计 ~~~ 事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据，来分辨出优略。 缺点： 1.必须先运行依据算法编制的程序 2.所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计： ~~~ 一个高级语言程序在计算机上运行所消耗的时间取决于： - 1.依据的算法选用何种策略 - 2.问题的规模 - 3.程序语言 - 4.编译程序所产生机器代码质量 - 5机器执行指令速度 注意：同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，——-使用绝对时间单位衡量算法效率不合适 ### 算法的时间和空间复杂性 ##### 时间复杂度（Time Complexity） 设算法中所有语句的语句频度为t(n),f(n)是当n趋向无穷大时与t(n)为同阶无穷大，则 算法的时间复杂度T(n)=O(f(n)) 其中：n为算法计算量或成为规模（size）; f(n)是运算时间随n增大时的增长率； O(f(n))是算法时间特性的量度。 算法分析主要从 分析算法的时间复杂度、空间复杂度这两个方面以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故作算法的时间复杂度作为分析的重点。算法执行时间T(n)的数量级称为算法的渐近时间复杂度，T(n)=O(f(n)),它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度。  ~~~ i=1; ① while (i<=n) i=i*2; ② 解： 语句1的频度是1, 设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n 取最大值f(n)=log2n, T(n)=O(log2n ) ~~~ 常见的时间复杂度按照数量级递增排序依次为：常数阶O(1)、对数阶O(log2 n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、K次方阶O(n^k)、指数阶O(2^n)。 > 愚公移山固然可敬，但发明推土机和炸药，更加实在和聪明。希望大家在今后的学习中，好好利用算法分析的工具，改进自己的代码，让计算机轻松一点，这样你就能更胜一筹.