Abo

数据结构概论


数据结构与算法绪论,打算将当初的数据结构笔记搬上博客,主要参照《大话数据结构》,此处强烈推荐


fade


摘要图存粹是为了美观,其次是为了推荐这首faded的remix,同一首歌不一样的感觉,在我看来,多了一种空灵的美感,强烈推荐,之后的摘要图估计也会是图文关系不大( ̄︶ ̄)↗ 


        

数据结构:是相互之间存在的一种或多种特定关系的数据元素的集合。

  • 逻辑结构:数据对象中数据元素之间的相互关系
    1. 集合结构(平等)
    2. 线性结构(一对一)
    3. 树形结构(一对多)
    4. 图形结构(多对多)
  • 物理结构:数据的逻辑结构在计算机中的存储方式
  1. 顺序结构
  2. 链式结构

算法(Algorithm):对数据结构的运用

  • 算法的特性
  1. 输入:算法具有零个或多个输入
  2. 输出:算法至少有一个或多个输出
  3. 有穷性:自动结束不会死循环
  4. 确定性:不会出现二义性
  5. 可行性:每一步都是可行的
  • 算法设计要求
  1. 正确性
    1. 算法程序没有语法错误
    2. 算法程序对于合法的输入数据能够产生满足要求的输出结果
    3. 算法程序对于非法的输入数据能够算得出满足规格说明的结果
    4. 算法程序对于精心选择的,甚至刁难的测试数据都有满足要求的输出结果
  2. 可读性
  3. 健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或者莫名其妙的结果
  4. 时间效率搞和存储量低

算法效率的度量方法

  1. 事后统计方法
  2. 事前分析估算方法

函数的渐近增长与时间复杂度

  • 大O阶方法
  1. 用常数1取代运行时间中所有加法常数
  2. 在修改后的运行次数函数中,只保留最高阶项
  3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数,得到的结果就是大O阶。
  • 常数阶

    无论n为多少,这个常数为多少,我们都记作O(1),而不能是O(3)、O(12)等任何数字,这是初学者常常犯的错。可以理解为常数项为最高项,然后去除系数,则为1

  • 线性阶

    1
    2
    3
    4
    5
    int i;
    for(i = 0; i < n;i++)
    {
    /*时间复杂度为O(1)的程序步骤序列*/
    }
  • 对数阶

    1
    2
    3
    4
    5
    6
    int count = 1;
    while(count < n)
    {
    count = count * 2;
    /*时间复杂度为O(1)的程序步骤序列*/
    }

由2^x^=n得x=log(2)n,所以这个循环的时间复杂度为O(logn)

  • 平方阶
    1
    2
    3
    4
    5
    6
    7
    8
    int i,j;
    for(i = 0; i < n;i++)
    {
    for(j = 0; j < n;j++)
    {
    /* 时间复杂度为O(1)的程序步骤序列*/
    }
    }
1
2
3
4
5
6
7
8
int i,j;
for(i = 0;i < n;i++)
{
for(j = i;j < n;j++) /*注意j = i而不是0*/
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}

总执行次数为:n+(n-1)+(n-2)+…+1= n^2^/2+n/2,因此这段代码的时间负责度为O(n^2^)

  • 最坏情况与平均情况
  1. 通常,除非特殊指定,我们提到的运行时间都是最坏情况的运行时间
  2. 平均运行时间是所有情况中最有意义的,因为它是期望的云习惯时间,但是平均运行时间和难通过分析得到,一般都是通过运行一定数量的实验数据后估算出来的。
  3. 一般在没有特殊说明的情况下,都是指最坏时间复杂度

算法空间复杂度