绪论

2020/1/28 10:52:16 人评论 次浏览 分类:学习教程

基本概念

数据
数据元素
数据对象
数据类型
抽象数据类型(ADT)
数据结构

数据元素之间的关系称为数据结构
.
数据结构包括逻辑结构,存储结构和数据的运算

逻辑结构(构想)

线性结构和非线性结构(集合,树,图)

存储结构(实现)

顺序结构(数组,连续存储)
链接结构(链表)
索引结构(索引表)
散列结构(哈希值计算)

运算

  • 运算的定义
  • 运算的实现

算法和算法评价

算法

解决特定问题的步骤
.

  • 有穷性(步骤有穷)
  • 确定性(结果确定)
  • 可行性(可以操作)
  • 输入
  • 输出

算法评价

时间复杂度

所有语句执行的次数和
主要考虑

  • 最坏时间复杂度
  • 最好时间复杂度
  • 平均时间复杂度

大O表示法,f(n)=O(g(n)),f(n)阶不高于g(n),上界

  • O(max(f,g))=O(f)+O(g)
  • O(f+g)=O(f)+O(g)
  • O(f*g)=O(f)*O(g)

Ω表示法,与大O定义相反,下界
θ表示法,确界

题型:给一段代码计算时间复杂度
基本方法:

  • 循环终止条件
  • 循环变量增加形式
  • 确定循环次数

小结论:

  • for(i=a;i<n^b;i=i*c)时间复杂度为O(logn)
  • for(i=a;i<n*b;i=i+c)时间复杂度为O(n)

题型:递归方程求时间复杂度
方法一:迭代
方法二:求通项,数列
方法三:主定理

空间复杂度
陈&sl
发布了12 篇原创文章 · 获赞 0 · 访问量 115
私信 关注

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->