第一章-基础概念

数据结构与算法的基础概念

数据结构

数据结构：数据元素的存储、组织方式

1.逻辑结构：线性结构（一对一）、树形结构（一对多）、图状结构（多对多）

​ 总结：“线性结构”和“非线性结构” 两大类。与“数据元素本身”没有关系，只与数据元素之间的联系有关。

2.存储结构：顺序存储、链式存储

​ 总结：描述实际存放数据元素的物理结构。与“数据元素本身”有关系。

3.逻辑结构与存储结构的关系：一种“逻辑结构”可以用多种“存储结构”来实现。

算法

1.特性（必须满足）：有穷、确定、可行、输入和输出

2.评价标准（越高越好）：正确、可读、健壮、高效

复杂度

最坏情况的复杂度（上限），用O(数量级)表示

1.时间复杂度

算法是否高效的评价标准

常见的时间复杂度：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)、O(n³) 从小到大排序

T(n)：表示时间函数，参数（输入规模）是n

题型一时间复杂度计算：口诀：只看最高次项，忽略系数和常数。

例1：T(n)=2n²+5n+3 =>O(n²)

解：最高次项为n²，忽略系数和常数，所以时间复杂度为O(n²)。

例2：在算法输入规模为n时，算法运行时间正比于9log(3ⁿ)，则该算法的时间复杂度为？

解：9log(3ⁿ)=9nlog3，9和log3都是常数，所以时间复杂度为O(n)。

题型二分析算法程序的复杂度：①看输入，②找上限（循环次数的上限）

例1：分析下列算法（程序段）的时间复杂度，算法输入：n和m

int ans = 0;
for (int i = 0; i < n; i += 1) {
    for(int j = 0; j < m; j += 1) {
        ans += 1;
    }
}

解：

①看输入，得知输入规模为n和m。所以参数为n和m这两个。

②找上限（循环次数的上限），外层for循环的i的上限是n，内层for循环的j的上限是m，因此会循环nm次，所以时间复杂度为O(nm)。

例2：分析下列算法（程序段）的时间复杂度，算法输入：大小为n的数组nums、一个整数val

for (int i = 0; i < n; i += 1) {
    if (nums[i] == val) {
        return i;
    }
}

解：

①看输入，得知输入规模实际上就是n。所以参数为n。

②找上限（循环次数的上限），因为i<n，所以nums[i]的i的上限为n，最坏的情况要执行n次，才能使得nums[i]==val，所以时间复杂度为O(n)。

例3：分析下列算法（程序段）的时间复杂度，算法输入：n

int ans = 0;
for (int i = 0; i < n; i += 1) {
    for(int j = 1; j < i; j *= 2) {
        ans += 1;
    }
}

解：

①看输入，得知输入规模为n，所以参数为n。

②找上限（循环次数的上限），因为i<n，所以i的上限为n，因此外层for循环的时间复杂度是O(n)，又因为j<i，所以j的上限也为n，得知j的范围是1~n，又因为j *= 2，所以j是1248...n。设x为循环次数，可知规律是2ˣ=n，所以x=log₂n，因此内层for循环的时间复杂度是O(log₂n)，可简写成O(logn)。内外层是嵌套关系，复杂度相乘，得到总复杂度为O(nlogn)。

例4：分析下列算法（程序段）的时间复杂度，算法输入：n

int ans = 0;
for (int i = 0; i <= n; i += 1) {
    if (i > 1000) {
        break;
    }
    ans += i;
}

解：

①看输入，得知输入规模为n，所以参数为n。

②找上限（循环次数的上限），因为i<n，所以i的上限为n，但又因为if (i > 1000)，所以i的上限最多为1000，大于1000就退出了。1000是常量，所以时间复杂度为O(1)。

2.空间复杂度

常见的复杂度：O(1)、O(n)