• 算法设计与分析之算法绪论


    • 学习目标
      • 设计高效的算法
      • 分析算法的性能
      • 在分析与交互中验证算法
    • 参考书:算法导论

    1、算法定义

    • 算法定义:给定计算问题,算法是一系列良定义的计算步骤,逐一执行计算步骤即可得到预期的输出。
      • 计算问题:给定数据输入,计算满足某种性质输出问题
    • 算法的性质
      • 有穷性:算法必须在有限个计算步骤后终止。
      • 确定性:算法必须是没有歧义的。
      • 可行性:可以机械的一步一步执行基本的操作步骤。

    2、算法的表示

    • 自然语言
      • 优势:以近于人的思维,易于理解主旨
    • 编程语言
      • 优势:精准表达逻辑,规避表述歧义
      • 不便之处:不同的编程语言间语法存在差异,过于关注算法实现的细枝末节
    • 伪代码
      • 非正式语言
        • 移植编程语言书写形式作为基础和框架
        • 按照接近自然语言的形式表达算法过程
      • 兼顾自然语言与编程语言优势
        • 简洁表达算法本质,不拘泥于实现细节
        • 准确反映算法过程,不产生矛盾和歧义

    3、算法分析

    • 算法分析的原则

      • 统一机器性能
      • 分析最坏情况
    • 机器的运算速度影响算法的执行时间

      • 归纳基本操作
      • 统一机器性能
    • 相同的输入规模,实例影响运行

      • 例:插入排序(升序排序)最好情况:数组升序,最坏情况:数组降序
        在这里插入图片描述
    • 算法分析的工具

      • 渐近分析:忽略 T ( n ) T(n) T(n)的系数与低阶项,仅关注高阶项,用记号 θ \theta θ表示
        在这里插入图片描述
      • 渐近记号
        在这里插入图片描述
      • 渐近紧确界
        在这里插入图片描述
      • 渐近上界
        在这里插入图片描述
      • 渐近下界
        在这里插入图片描述

    4、例子

    • 插入排序与选择排序
      • 伪代码及时间复杂度分析
        在这里插入图片描述
    • 代码实现
    # 插入排序:将数组a分为有序和无序的两个部分。前者在左边,后者在右边。开始有序的部分只有a[0],其余都属于无序的部分。
    # 每次取出无序部分的第一个(最左边)元素,把它加入有序部分。假设插入合适的位置p,则原p位置及其后面的有序元素都向右移动一个位置,
    # 有序部分增加一个元素。一直做下去,直到无序部分没有元素
    def insert_sort(l):
        for i in range(len(l) - 1):
            key = l[i+1]  # 无序部分第一个值
            index = i
            while index >= 0 and l[index] > key:
                l[index+1] = l[index]
                index -= 1
            l[index + 1] = key
        return l
    
    # 选择排序:每次从待排序列中选出一个最小值
    def select_sort(l):
        for i in range(len(l)):
            for j in range(i+1, len(l)):
                if l[i] > l[j]:
                    temp = l[i]
                    l[i] = l[j]
                    l[j] = temp
        return l
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
  • 相关阅读:
    Flex 布局项目实战,好像没那么难!
    PX4模块设计之十九:Replay模块
    尚硅谷–MySQL–基础篇(P1~P95)
    Redis 哨兵模式网络问题:Unable Connect
    【Android 系统】recovery字体大小修改
    Spring MVC框架看这篇就够了
    Python5
    C++ 指针的算术运算
    外贸客户开发信怎么写?如何撰写营销邮件?
    统计信号处理基础 习题解答10-6
  • 原文地址:https://blog.csdn.net/qq_38689352/article/details/126483476