数据结构与算法(0.定义)

01 Aug 2022 in Posts / Algorithm

数据结构与算法(1.定义)

• 1. 数据结构定义
  • 1.1 逻辑结构
    • 1.1.1 集合( N )
    • 1.1.2 线性( 1 : 1 )
    • 1.1.3 树( 1 : N )
    • 1.1.4 图( N : N )
  • 1.2 存储结构
    • 1.2.1 顺序存储
    • 1.2.2 链式存储
• 2. 算法
  • 2.1 特征
  • 2.2 评价标准
  • 2.3 效率
    • 2.1. 时间复杂度
    • 2.2. 空间复杂度

1. 数据结构定义

1.1 逻辑结构

1.1.1 集合( N )

数据元素间的关系是“属于同一个集合”.

1.1.2 线性( 1 : 1 )

数据结构中的元素存在一对一的相互关系.

1.1.3 树( 1 : N )

数据结构中的元素存在一对多的相互关系.

1.1.4 图( N : N )

数据结构中的元素存在多对多的相互关系.

1.2 存储结构

1.2.1 顺序存储

数据在地址连续的存储单元中存储的结构.

1.2.2 链式存储

数据在地址离散的存储单元中存储的结构.

2. 算法

算法, 计算数据的方法.

2.1 特征

• 有穷
• 确定
• 可行

2.2 评价标准

• 正确
• 健壮
• 效率
• 可读

按照现在的开发环境来说, 可读这个标准很鸡肋, 因为算法本身就是有认知门槛的事情, ”水平不够看不懂, 可读不可读的问题, 是谁的问题?”, 环境很卷, 自嘲罢了.

2.3 效率

2.1. 时间复杂度

时间复杂度是以计算过程中的最高阶的一步算法来标记的值. \[O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)\]

// O(n)
void sum(int n){
    int i,sum = 0;               // 1
    for (i = 1; i <= n; i++) {   // 1
        sum += i;                // n
    }
    printf("sum: %d\n",sum);  //1
}

2.2. 空间复杂度

空间复杂度是以计算过程中所用辅助空间大小来标记的值.

最好理解的一个例子: 数组逆序

• 使用位移操作换位, 因为不需要辅助空间, 所以是O(1)
• 使用临时变量, 也是常数的辅助空间, 所以也是O(1)
• 使用另一个数组空间倒序遍历放入, 使用了数组容量相同的辅助空间, 所以是O(n)