大话数据结构 读书笔记

1. 绪论

逻辑结构

  • 集合结构
  • 线性结构
  • 树形结构
  • 图形结构

物理结构

  • 顺序存储结构
  • 链接存储结构

2. 算法

算法特征

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

算法时间复杂度

常数阶 O(1)

线性阶 O(n)

对数阶 O(logn)

1
2
3
4
5
int count =1;
while(count < n)
{
    count = count * 2;
}

${2^x} = n => x = log_2n$

平方阶 $O({n^2})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int i,j;
for (i = 0; i < m; i++)
{
    for (j= 0; j < n; j++)
    {
    /* 时 间 复 杂 度 为 0(1) 的 程序 步骤 序 列 */
    }
}

int i,j;
for(i = 0; i <n; i++)
{
for (j =i; j <n; j++) /* 注意j = i 而不 是0 */
{
/* 时间 复 杂 度为0(1) HBRP RAR */
}
}

$n+(n-1)+(n-2)+{\cdots}+1 =\frac{n(n+1)}{2}=\frac{n^2}{2}+\frac{n}{2}$

$O(n^2)$

常见时间复杂度

$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)< O(n!) < O(n^n)$

3. 线性表

Here is a footnote reference,[^1] and another.[^longnote]

Endnotes

[^1]: Here is the footnote.
[^longnote]: Here’s one with multiple blocks.