【趣学算法】第一章读书笔记

14天阅读挑战赛 *努力是为了不平庸~ 算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！

文章目录

• 1.1打开算法之门
• 1.2 妙不可言——算法复杂性
  • 算法的特性
  • 好算法的标准
  • 时间复杂度和空间复杂度
    • 时间复杂度
    • 空间复杂度
    • 宕机
• 1.4算法设计
• 总结

1.1打开算法之门

瑞士著名的科学家Niklaus Wirth教授曾提出：数据结构+算法=程序。 数据结构是程序的骨架，算法是程序的灵魂。

1.2 妙不可言——算法复杂性

算法是对特定问题求解步骤的一种描述。它不依赖于任何一种语言，既可以用自然语言、程序设计语言描述，也可以用流程图、框图来表示。

算法的特性

1. 有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。
2. 确定性：每条语句都有确定的含义、无歧义。
3. 可行性：算法在当前环境条件下可以通过有限次运算来实现。
4. 输入/输出：有零个或多个输入以及一个或多个输出。

好算法的标准

高效率、低存储

1. 正确性：算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期。
2. 易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。
3. 健壮性：算法对非法数据及操作有较好的反应和处理。
4. 高效性：算法运行效率高，即算法运行所消耗的时间短。
5. 低存储性：算法所需的存储空间小。算法如果占用空间过大，则无法运行。

时间复杂度和空间复杂度

时间复杂度

算法的时间复杂度就是算法运行需要的时间。 在实际应用中，通常使用时间复杂度渐近上界O(f(n))来表示时间复杂度。 注意：不是所有算法都能直接计算运行次数。 最坏情况对衡量算法的好坏具有实际意义。 常见的算法时间复杂度有常数阶、多项式阶、指数阶、对数阶

空间复杂度

算法的空间复杂度就是算法占用的空间大小。 算法占用的存储空间包括：输入/输出数据、算法本身、额外需要的辅助空间。 算法在运行时所使用的辅助变量占用的空间（即辅助空间）才是衡量算法空间复杂度的关键因素。

宕机

宕机就是死机，指计算机无法正常工作，包括一切原因导致的死机。计算机主机出现意外故障而死机，一些服务器死锁，服务器的某些服务停止运行等，都可以称为宕机。 设计算法时，我们要注意算法复杂度增量的问题，尽量避免爆炸级增量。

1.4算法设计

算法设计完后，需要考虑的问题：

• 算法是否正确？
• 算法复杂度如何？
• 算法能否改进？

总结

以上就是今天的学习啦~ 咱们下期再见~