算法

什么是算法?

通过一系列的计算步骤将输入数据转化为输出结果

算法的意义

解决某些特定的问题,同一个问题,不同算法的效率往往差距很大,有些时候这种差距的影响比硬件和软件方面的差距还要大

常用算法

• 排序算法
  • 冒泡算法
  • 插入排序
  • 希尔排序
  • 快速排序
  • 选择排序
  • 堆排序
  • 归并排序
  • 基数排序
• 加密算法

算法特征

• 有穷性
  执行有限个步骤之后终止
• 确切性
  每一步都有确切的定义
• 输入
  存在n个输入 (n>=0)
• 可行性
  任何计算步骤都可以被分解为基本的可执行操作,也就是说每个计算步骤都可以在有限时间内完成

如何评判算法的优劣

• 正确性
• 可读性
• 健壮性(对不合理输入的反应和处理能力)
• 时间复杂度(估算程序指令的执行次数)
• 空间复杂度(估算所需占用的存储空间)

为什么不能单从效率上进行评估

• 单从效率来比较是不同算法对同一组输入输出的执行处理时间
• 执行时间严重依赖硬件以及运行时各种不确定环境因素
• 必须编写相对应的测算代码
• 测试数据的选择比较难保证公正性

算法的复杂度

• 大O表示法

  
  image.png

• 常见复杂度

  
  image.png

• 常见排序算法的复杂度

  
  image.png

算法的优化

• 内存空间尽量少
• 执行步骤尽量少
• 在合适的情况下进行空间和时间上的转换