大话数据结构1-时间复杂度

发表于 2020-10-22 更新于 2021-01-10 分类于 1- 编程相关，数据结构与算法阅读次数： Valine：

I 引子

想学习一些数据结构与算法相关的内容，选择了这本读起来会比较轻松的《大话数据结构》。前言部分，作者给出了一些阅读的建议，包括：

虽然也是老生常谈的学习经验，不过常常为了追求学习速度，而忽略知识掌握扎实的重要性，在这里被作者再次提醒一下，也是非常不错的。

此外，作者提到，由于本书是使用 C 语言实现的，对于java 使用者，对于文中的 struct 以及针对结构的参数传递的代码可以理解为类的定义和由类生成的对象的传递。虽然存在差异，但不影响整体知识的理解。

在引言的最后，作者谈到了初学者常见的一个疑问：在编程语言的开发包中，主要的数据结构：栈、队列、链表等都有实现，并且常见的查找算法、排序算法也有现成的接口，那为什么还要去深入了解里面的算法原理呢？看完本书，我们应该就可以得到答案。

学习一个门类的知识，我们应该首先对其有一个概念上的了解。那什么是”数据结构”,什么是”算法”呢？我们给出如下定义。（是什么）

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

算法是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

从本质上讲，程序是通过处理输入的数据，并最终向人们展示一个结果的工具，而怎样高效的处理数据，则首先需要将数据做好整理，再通过巧妙的计算方法得到最终的运算结果，因此：（为什么）

可以说，好的程序设计就是首先选择一种好的数据组织结构，然后再利用一种低消耗的算法来进行数据的运算、移动。

实际上，算法与数据结构的思想，同样适用于公司管理（=好的组织架构+高效协同工作），以及个人的知识提升（知识整理+知识运用）。

更具体一些，通常有哪些数据的组织结构呢？分别从逻辑结构和物理存储结构两个方面进行分析，我们有如下分类：

逻辑结构可以分为下面几种：集合结构；线性结构（1对1）；树形结构（1对多）；图形结构（多对多）。

物理结构，数据的逻辑结构再计算机中的存储形式：顺序存储结构（连续的地址储存单元中）；链式存储结构（储存地址不连续，通过存储下一个单元的指针来实现）

根据数据的特点和我们的需求，将数据组织好之后，则是对数据进行移动、运算，那什么影响运算的效率呢？我们考虑如下几点：

算法消耗时间因素：1-算法采取的策略，方法；2-编译器产生的代码质量（编译环节）3- 机器执行指令的速度（CPU）。

可以看出，算法不仅受设计者的影响，还与底层的编译器，以及硬件运算能力有关。

既然算法与数据结构如此的重要，那么我们怎么评价一个算法与结构的优劣呢？最简单的，我们可以通过算法的实际运行效果来判断，但是这通常是低效的。预先估计好算法的运行效果，才是高效的程序设计过程。因此，我们引入一种粗略估算法性能的方法：时间复杂度分析。在这之前，我们先看一个概念:

函数的渐近式增长

给定两个函数 $f(n)$ 和 $g(n)$，如果存在一个整数 $N$，使得对于所有的 $n>N$， $f(n)$ 总是大于 $g(n)$，我们说 $f(n)$ 的增长渐近快于 $g(n)$。

对于一个可变的变量$n$，算法的执行时间会受到 $n$ 的大小的影响（例如用最笨的方法计算从1加到n，需要运算的次数等于n）。通常的，我们更加关注最坏的运行情况，也就是 $n$ 非常大的情况，在这种情况下，运行时间不会再坏，是程序运行的一种时间上的保证。

因此，根据上面的渐近增长函数模型，我们判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

一般的，我们用大O记法表示算法时间复杂度，具体推导方法如下：

常见的时间复杂度有，常数阶 O(1), 线性阶 O(n)**，平方阶 **O($n^2$)**，对数阶 **O($logn$) .. 他们之间有如下的排序：

$$O(1)< O(log(n))< O(n)< O(nlog(n))< O(n^2)< O(n^3)< O(2^n)< O(n!)< O(n^n)$$

例子：

嵌套循环

int i, j;
for (i = 0; i < n; i++){
    for (j = i; j < n; j++){
        //时间复杂度为 $O(1)$ 的程序步骤
    }
}

共执行：$\frac{n(n+1)}{2} = \frac{n^2}{2}+\frac{n}{2}$ 次，因此，时间复杂度为 $O(n^2)$.