1.1 数据结构基本概念
数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合
1.2 基本结构
数据元素相互之间的关系称为结构,数据元素之间关系的不同特性,4类基本结构:1. 集合 2. 线性结构 3. 树形结构 4. 图状结构或网状结构
1.3 基本原理
1.4 基本方法
1.5 存储结构
顺序存储结构、链式存储结构
1.6 基本操作
1.7 时间复杂度
T(n) = O(f(n)) 基本操作执行次数是问题规模n的讴歌函数f(n) 问题规模n增大,算法执行时间的增长率和f(n)的增长率相同 频度(frequency count) 指该语句重复执行的次数 a {++x; s = 0;} b for (i=1; i<=n; ++i) {++x; s += x;} c for (j=1; j<=n; ++j) for (k=1;k<=n;++k) {+=x; s += x;} d for(i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i][j] = 0; for (k=1; k<=n; ++k) c[i][j] += a[i][k] * b[k][j]; } 其中abcd分别对应时间复杂度为 O(1) O(n) O(n^2) O(n^3) d是求n x n 矩阵相乘 我们应该金肯呢个选用多项式阶O(n^k)的算法,而不希望用指数阶的算法。除特别指明外,均指最坏情况下的时间复杂度。
1.8 空间复杂度(space complexity)
S(n) = O(f(n))
其中n为问题的规模(或大小),S(n)算法所需存储空间的量度