算法

第五章、算法

计算机科学的核心是算法核心

• 许多研究人员相信，人脑中的活动，包括幻想、创造和决策，实际上都是算法的执行结果

1. 算法的正式定义

可终止过程的一组无歧义的、可执行的步骤的有序集合

• 当然包也有不确定算法
• 同样有那些用算法无法解决的问题

2. 算法的抽象本质

• 程序是一个算法，算法的表示方式有很多种，比如数学公式，图解等

3. 求解问题的艺术

• 在求解问题之前，需要充分理解问题的(虽然在解决问题之前难以真正地理解问题，所以这两种情况应该相辅相成)，避免造成资源浪费

• 对于一个还没有完成的任务，然后去做其他事情，可能会在完成其他事情之前就想到刚刚问题的解决方案(沉思期)，潜意识在不断地工作

3.1 卖迈出第一步

• 就是动手解决现在能够解决的问题

  逐步求精

• 将问题分为多个子问题，逐步解决，也就是自顶向下

• 自顶向下和自底向上是计算机科学中终重要的方法

4. 迭代结构

一组指令以循环的方式重复执行

4.1 顺序搜索算法

• 按照顺序进行查找

4.2 循环控制

• 前测试循环（pretest loop）
• 后测试循环（posttest loop）

4.3 插入排序算法

• 在一个存在的序列里面进行排序，并不大量使用其他空间

4.4 递归结构

迭代和递归的等价性

二分查找

def search(List, targetValue):
    listLen = len(List)
    if (listLen == 0):
        return -1
    else:
        testEntry = List[listLen/2]
        if (testEntry == tatgetValue):
            return list/2
        if (testEntry > tatgetValue):
            newList = List[listLen/2 + 1:]
            search(newList, targetValue)
        if (testEntry < tatgetValue):
            newList = List[:listLen/2 - 1]
            search(newList, targetValue)

4.5 递归控制

• 必须要有一个能够结束递归的条件，否则将陷入无限地调用

5. 效率和正确性

5.1 算法效率

时间复杂度和空间复杂度

• 对于二分查找的效率为 $$ log_2 n $$

5.2 软件验证

例子

一位拿着由7个金环组成的链子的旅行者必须在一个酒店里住7也，每一夜的 租金是金链中的一环，应该怎样对链子进行最少次数的切割，旅行者才能每天早 上支付饭店的一环而不用提前支付住宿费？

解决

只要切开第三环即可，通过不断地交换金环就行了

思考

正确的程序往往和我们的想法一些出入，那些看似正确的方法离真正的解决方案还是有一段距离的，目标是用形式逻辑来证明程序表达的算法确实做了它试图做的工作

质量的优秀十分依赖于测试，断言（assertion）

最后更新： 2018年07月11日 14:15

原始链接： https://ilifexiao.github.io/2018/06/07/计算机科学概论/第五章、算法/

xiao