美文网首页
数据结构与算法 --- 基础

数据结构与算法 --- 基础

作者: 凌云01 | 来源:发表于2020-07-02 22:22 被阅读0次

    一、基础篇

    1、数据结构基本术语

    • 数据:程序的操作对象,用于描述客观事物。
      特点: 1.可以输入到计算机。2.可以被计算机处理。
    • 数据对象:性质相同的数据元素的集合(类似于数组)。
    • 数据元素:组成数据对象的基本单位。
    • 数据项:一个数据元素由若干数据项组成。
    image.png
    • 结构: 数据元素之间不是独立的,存在特定的关系.这些关系即是结构;
    • 数据结构: 指的数据对象中的数据元素之间的关系

    2、逻辑结构和物理结构

    2.1、逻辑结构

    数据对象中数据元素之间的逻辑关系。分为四种:

    • 集合结构
      集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。各个数据元素是"平等"的。

    • 线性结构
      数据和数据之间一对一关系
      常见:线性表、站、队列、字符串

    • 树形结构
      数据和数据之间一对多关系

    • 图形结构
      数据和数据之间多对多关系

    2.2、物理结构

    物理结构: 又称“存储结构”,指的是数据的逻辑结构在计算机的存储形式。

    • 顺序存储结构
    • 链式存储结构
      不需要提前开辟连续空间

    二、算法基础

    算法: 算法就是解决特定问题求解步骤描述,在计算机中表现为指令的有限序列, 并且每个指令表示一个或多个操作.

    算法特性:

    • 输⼊输出
    • 有穷性
    • 确定性
    • 可行性

    设计要求(评价标准)

    • 正确性
    • 可读性
    • 健壮性
    • 时间效率⾼高和储存量量低

    1、复杂度

    1.1时间复杂度

    大O表示法

    1. 用常数1取代运行时间中所有常数 3->1 O(1)
    2. 在修改运行次数函数中,只保留最高阶项 n3+2n2+5 -> O(n^3)
    3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
    image.png

    O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

    1.2空间复杂度

    算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式 记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句句关于n所占存储空间的函数。

    相关文章

      网友评论

          本文标题:数据结构与算法 --- 基础

          本文链接:https://www.haomeiwen.com/subject/wgsdqktx.html