数据结构-1:绪论

2021-04-10
709字
2分钟

数据结构-1:绪论

绪论

数据结构

逻辑结构

四大结构

  • 集合结构:其中元素除了同属于同一个集合,没有其他关系

  • 线性结构:数据结构是一对一的关系

  • 树形结构:元素之间存在一种一对多的关系

  • 图形结构:元素是多对多的关系

物理结构

数据在存储器中的结构

  • 顺序存储结构:把数据元素存储在地址连续的存储单元里
  • 链式存储结构:把数据元素放在任意的存储单元里,需要一个指针存放元素的地址

算法

算法与数据结构紧密相连

算法的五个特征:

  • 输入:具有零个或多个输入
  • 输出:算法至少有一个输出(打印或返回)
  • 有穷性:算法在执行有限的步骤之后,结束而不会无限循环,并且每一个步骤在可以接受的时间内完成
  • 确定性:每一个步骤都有确定的含义,没有二义性;一定条件下的执行路径唯一;每个步骤定义精确
  • 可行性:每一步都可以实现

算法设计的要求

  • 正确性:就算对
    • 没有语法错误
    • 对于合法输入能产生满足要求的输出
    • 对于非法输入能产生满足规格的说明
    • 对于故意刁难的测试输入都有满足要求的输出结果?
  • 可读性:便于阅读理解交流
  • 健壮性:输入数据不合法也能做出相关处理,不会崩溃
  • 时间效率高和储存量低

复杂度

效率与什么有关

算法的效率往往取决于:

  • 算法采用的策略、方案
  • 编译产生的代码质量
  • 问题的输入规模
  • 机器执行指令的速度

抛开环境,效率与算法优劣输入规模有关

效率的计算方法

事后统计方法:实际运行测量时间

环境不同,浪费时间

事前估算方法

函数的渐进增长

给定两个函数$f(n)$和$g(n)$,如果存在一个整数$N$,使得对于所有的$n>N$,$f(n)$总是比$g(n)$大,我们说$f(n)$的增长渐进快于$g(n)$。

时间复杂度

大O表示法:渐进时间复杂度

用常数1取代运行时间中所有的加法常数

值保留最高项

去掉最高阶的常数

空间复杂度

Avatar
Zhang.Mathias 巧者劳而智者忧,无能者无所求,饱食而遨游,泛若不系之舟