如何评定一个算法的好坏

  • 如果单从执行效率上进行评估，可能会想到这么一种方案

    • 比较不同算法对同一组输入的执行处理时间
    • 这种方案也叫做：事后统计法

  • 上述方案有比较明显的缺点

    • 执行时间严重依赖硬件以及运行时各种不确定的环境因素
    • 必须编写相应的测算代码
    • 测试数据的选择比较难保证公正性
  • 一般从以下维度来评估算法的优劣
    • 正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
    • 时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
    • 空间复杂度（space complexity）：估算所需占用的存储空间

大O表示法（Big O）

  • 一般用大O表示法来描述复杂度，他表示的是数据规模n对应的复杂度
  • 忽略常数、系数、低阶

    注意：⼤O表⽰法仅仅是⼀种粗略的分析模型，是⼀种估算，能帮助我们短时间内了解⼀个算法的执⾏效率