数据结构 - 算法

12/29/2020 数据结构Java

什么是算法?

  • 程序 = 数据结构 + 算法
    • 数据结构:如何把现实世界的问题信息化,将信息存进计算机,同时还有实现对数据结构的基本操作。
    • 如何处理这些信息,以解决实际问题

算法的特性

  • 有穷性 一个算法必须总在执行的有穷步之后结束,且每一步都可在有穷时间内完成。 注意:算法必须是有穷的,程序可以是无穷的
  • 确定性 算法中的每条指令必须有确切的含义,对于==相同的输入==只能得出==相同的输出==
  • 可行性 算法中描述的操作都可以通过已经实现的==基本运算执行有限次==来实现
  • 输入 一个算法有==零个或多个输入==,这些输入取自某个特定的对象的集合
  • 输出 一个算法有==一个或多个输出==,这些输出是与输入有着某种特定的关系的量

“好”算法的特性

  • 正确性: 算法应能够正确地解决求解问题
  • 可读性 算法应该具有良好的可读性,以帮助人们理解。 注:算法可以使用伪代码来表示,甚至可以用文字来表示
  • 健壮性 输入非法数据时,算法能适当的做出现反应或进行处理,而不会产生莫名其妙的输出结果。
  • 高效率与低存储量需求
    • 执行速度快,时间复杂度低。
    • 不占用内存,空间复杂度低。

算法效率的度量

怎么来评估算法的时间开销? 让算法先运行,事后统计运行时间!

  • 存在的问题?
    • 和机器性能有关
    • 和编程语言有关
    • 和编程程序产生的机器指令质量有关
    • 有些算法是不能够使用事后统计的,如:导弹控制算法

时间复杂度

T1(n)=O(n)T_1(n)=O(n)

T2(n)=O(n2)T_2(n)=O(n^2)

T3(n)=O(n3)T_3(n)=O(n^3)

  • 加法规则

    T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

    多项相加,只保留最高阶的项,且系数变为1

  • 乘法规则

    T(n)=T_1(n)+T_2(n)=O(f(n))×O(g(n))

    多项相乘,都保留

    O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<o(2n)<O(n!)<O(nn)O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<o(2^n)<O(n!)<O(n^n)

    常对幂指阶

  • 结论1: 顺序执行的代码只会影响常数项,可以忽略
  • 结论2: 只需挑循环中的一个基本操作分析它的执行次数与n的关系即可
  • 结论3: 如果多层嵌套循环,只需要关注最深层循环了多少次

在很多算法中执行时间与输入的数据有关

  • 最坏时间复杂度 √ 最坏情况算法的时间复杂度
  • 平均时间复杂度 √ 所有输入示例等概率出现的情况下,算法的期望运行时间
  • 最好时间复杂度 最好情况下的算法的时间复杂度 算法

空间复杂度

  • 普通程序
    • 找到所占空间大小与空间规模相关的变量
    • 分析所占内存x与问题规模n的关系x=f(n)
    • x的数量级O(x)就是算法空间复杂度S(n)
  • 递归程序
    • 找到递归调用的深度x与问题规模n的关系x=f(n)
    • x的数量级O(x)就是算法空间复杂度S(n)
    • 注意:有点算法各层函数所需存储空间不同,分析策略也有区别

image-20210131155836772

Last Updated: 8/21/2021, 2:08:30 PM