《大话数据结构》第二章、算法

第二章、算法

算法就是解决特定问题的步骤描述，可以理解为我们将某个特定问题的求解步骤，每一步都用具有意义的，在一定时间内能够完成的代码进行描述。

算法的特性

• 输入：无 / 多个
• 输出：至少一个
• 有穷性：会在执行完有限步骤后自动结束，不陷入死循环
• 确定性：每一步具有确定意义，不具有歧义
• 可行性：每一步能够执行有限次数完成

算法设计要求

• 正确性：①没有语法错误；②对于合法输入，能有对应输出；③对于非法输入，也能有对应输出（错误提示）
• 健壮性：能够对非法输入做出处理
• 可读性：便于理解
• 时间效率高和存储量低

---

算法时间复杂度

程序运行时间，依赖于算法好坏和问题输入规模。我们考察算法的时间复杂度，是看随着问题输入规模的增大，算法运行时间会呈现何种方式的增加。通常使用O（）来记录时间复杂度。

用如下的步骤，我们就可以求得算法的时间复杂度

推导O()的步骤
1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数函数中，只保留最高阶项；
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

例如，下面这个算法的时间复杂度为什么是O(1)而不是O(3)，就是因为第一条原则

下面是常见的时间复杂度

Donate