一、复杂度分析

  1. 算法效率评估
    • 时间效率和空间效率是衡量算法优劣的两个主要评价指标。
    • 我们可以通过实际测试来评估算法效率，但难以消除测试环境的影响，且会耗费大量计算资源。
    • 复杂度分析可以消除实际测试的弊端，分析结果适用于所有运行平台，并且能够揭示算法在不同数据规模下的效率。
  2. 时间复杂度
    • 时间复杂度用于衡量算法运行时间随数据量增长的趋势，可以有效评估算法效率，但在某些情况下可能失效，
      如在输入的数据量较小或时间复杂度相同时，无法精确对比算法效率的优劣。
    • 最差时间复杂度使用大O符号表示，对应函数渐进上界，反应当n趋向正无穷时，操作数量T(n)的增长级别。
    • 推算时间复杂度分为两步，首先统计操作数量，然后判断渐进上界。
    • 常见时间复杂度从低到高排列有O(1)，O(log n)，O(n)，O(n log n)，O(n²)，O(2𝑛)，O(n!)等。
    • 某些算法的时间复杂度非固定，而是与输入数据的分布有关。时间复杂度分为最差、最佳、平均时间复杂度，
      最佳时间复杂度几乎不用，因为输入数据一般需要满足严格条件才能达到最佳情况。
    • 平均时间复杂度反应算法在随机数据输入下的运行效率，最接近实际应用中的算法性能。计算平均时间复杂度
      需要统计输入数据分布以及综合后的数学期望。
  3. 空间复杂度
    • 空间复杂度的作用类似于时间复杂度，用于衡量算法占用内存空间随数据量增长的趋势。
    • 算法运行过程中的相关内存空间可分为输入空间、暂存空间、输出空间。通常情况下，输入空间不纳入空间复杂度计算。
      暂存空间可分为暂存数据、栈帧空间和指令空间，其中栈帧空间通常仅在递归函数中影响空间复杂度。
    • 我们通常只关注最差空间复杂度，及统计算法在最差输入数据和最差运行时刻下的空间复杂度。
    • 常见空间复杂度从低到高排列有O(1)，O(log n)，O(n)，O(n²)，O(2^𝑛)等。

二、数据结构

  1. 数据结构的分类
    常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图，他们可以从”逻辑结构”和”物理结构”两个维度进行分类。
    1.1 逻辑结构：线性与非线性

    • 线性数据结构：数组、链表、栈、队列、哈希表，元素之间是一对一的顺序关系。
    • 非线性数据结构：树、堆、图、哈希表。
    • 树形结构：树、堆、哈希表，元素之间的一对多的关系。
    • 图，元素之间是多对多的关系。

    1.2 物理结构：连续与分散

    • 系统通过内存地址来访问目标位置的数据。
    • 物理结构反应了数据在计算机内存中的存储方式。
    • 所有数据结构都是基于数组、链表或者二者的结合实现的。
    • 基于数组可实现： 栈、队列、哈希表、树、堆、图、矩阵、张量（维度≥3的数组）等。
    • 基于链表可实现： 栈、队列、哈希表、树、堆、图等。

  2. 基本数据类型

    • 基础数据类型是CPU可以直接进行运算的类型。
      • 整数类型byte、short、int、long。
      • 浮点数类型float、double，用于表示小数。
      • 字符类型char，用于表示各种语言的字母、标点甚至表情符号等。
      • 布尔类型bool，用于表示”是”与”否”判断。
    • 基础数据类型是以二进制的形式存储在计算机中。
      • 在Python中，整数类型int可以是任意大小，只受限于可用内存；浮点数float是双精度64位；没有char类型
        单个字符实际上是长度为1的字符串str。

  3. 数字编码*
    3.1 原码、反码和补码

    • 原码：我们将数字的二进制表示的最高位视为符号位，其中0便是正数，1表示负数，其余位数表示数字的值。
    • 反码：正数的反码与其原码相同，负数的反码是对其原码除符号位外的所有位取反。
    • 补码：整数的补码与其原码相同，负数的补码是在其反码的基础上加1。
    • 负数的原码不能直接参与计算，例如：1+（-2）
      1+（-2）
      -> 0000 0001 + 1000 0010
      = 1000 0011
      -> -3
      计算机引入反码：
      1+（-2）
      -> 0000 0001 + 1000 0010 原码
      = 0000 0001 + 1111 1101 反码
      = 1111 1110 反码
      = 1000 0001 原码
      -> -1
    • 数字零的原码有+0和-0两种表达方式
      -0 -> 1000 0000 原码
      = 1111 1111 反码
      = 1 0000 0000 补码
      在负零的反码基础上加1会产生进位，但byte的类型长度只有8位，因此溢出的第九位会被舍弃
    • 计算机内部的硬件电路主要是基于加法运算设计的。

    3.2 浮点数编码

    • 32位长度的float由一下三个部分构成：

    • 符号位S： 占1位

    • 指数位E： 占8位

    • 分数位N： 占23位
      val=(−1)^𝑏31 ×2^(𝑏30𝑏29…𝑏23)2−127×(1.𝑏22𝑏21…𝑏0)2

  4. 小结

  • 数据结构可以从逻辑结构和物理结构两个角度进行分类，逻辑结构描述了数据元素之间的逻辑关系，
    而物理结构描述了数据在计算机内存中的存储方式。
  • 常见的逻辑结构包括线性、树状和网状等，通常我们根据逻辑结构将数据结构分为线性（数组、链表、栈、队列）和
    非线性（树、图、堆）两种，哈希表的实现可能同时包含线性数据结构和非线性数据结构。
  • 当程序运行时数据被存储在计算机内存中，内个内存空间都拥有对应的内存地址，程序通过这些内存地址访问数据。
  • 计算机中的基本数据结构类型包括整数byte、short、int、long，浮点数float、double，字符char和布尔bool。
    他们的取值范围取决于占用内存空间大小和表达方式。
  • 原码、反码和补码是在计算机中编码数据的三种方法，它们之间可以相互转换。整数的原码最高位是符号位，其余位是数字的值。
  • 整数在计算机中是以补码的形式存储的。在补码表示下，计算机可以对正数和负数的加法一视同仁，
    不需要为减法操作单独设计特殊的硬件电路，并且不存在正负零歧义的问题。
  • 浮点数的编码由1位符号位，8位指数位和23位分数位构成，由于存在指数位，因此浮点数的取值范围远大于整数，代价是牺牲了精度。
  • ASCII码是最早出现的英文字符集，长度为1字节，共收录127个字符。GBK字符集是常用的中文字符集。
    共收录两万多个汉字。Unicode致力于提供一个完整的字符集标准，收录世界上各种语言的字符，从而解决由于字符编码方法不一致而导致乱码的问题。
  • UTF-8是最受欢迎的Unicode编码方法，通用性非常好。它是一种变长的编码方法，具有很好的扩展性，有效提升了存储空间的石红效率。
    UTF-16和UTF-32是等长的编码方法，在编码中文时，UTF-16占用的空间比UTF-8更小。Java和C#等编程语言默认使用UTF-16编码。