首页 > 代码库 > 第二章 算法

第二章 算法

算法定义

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

 

 

算法的特性

  • 输入输出
    • 算法具有零个或多个输入,至少有一个输出
  • 有穷性
    • 算法在执行有限步骤后自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成
  • 确定性
    • 算法的每一步都具有确定的含义,不会出现二义性
  • 可行性
    • 算法的每一步都是可行的,也就是说每一步都能通过执行有限步骤的次数完成

 

 

算法设计的要求

  • 正确性
    • 指算法至少应该具有输入输出,能得到问题的正确解
    • 算法正确的四个层次:
      • 程序没有语法错误
      • 对于合法输入能够得到满足要求的输出结果
      • 对于非法输入能够识别并进行有效处理,而非程序异常退出
      • 对于精心选择、故意刁难的测试数据都能得到正确结果
  • 可读性
    • 结构化+见名知意+注释,便于阅读、理解和交流
  • 健壮性
    • 输入数据不合法时,也能做出相关处理,而不是产生异常或莫名其妙的结果
  • 高效性
    • 事件效率高,存储量低,用最短的时间和最少的内存空间处理大量数据

 

 

时间复杂度

技术分享

技术分享

一般时间复杂度不能超过平方阶,立方阶及以上都是不现实的。

平均时间复杂度,最坏时间复杂度

时间换空间,空间换时间

如果算法执行所需的辅助空间和输入规模无关是个常数,则称此算法是原地工作,空间复杂度是O(1)

 

 

 

 

 


 

    利用算法改进代码,让计算机轻松一些,这样才能胜人一筹。

 

第二章 算法