架构师训练营 Week8 作业总结

本周主要写关于数据结构与算法得学习总结。

数据结构与算法

1、时间复杂度与空间复杂度

1）、时间复杂度：不是程序具体运行的时间，而是算法中语句的执行次数。

①、多项式时间复杂度：O(1)、O(logn)、O(n^a)

②、非多项式时间复杂度：O(a^n)、O(n!)

③、常见算法的时间复杂度

2）、空间复杂度：一个算法在运行过程中临时占用存储空间大小的量度。

2、NP 问题

• P 问题：P 问题是一个判定问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模 n 的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于 P 类问题。P 类问题就是所有复杂度为多项式时间的问题的集合。确定一个问题是否是多项式问题，在计算机科学中非常重要。已经证明，多项式问题是可解问题，因为除了 P 问题之外的问题，其时间复杂度都很高，即求解需要大量时间。

• NP 问题：NP 问题是指可以在多项式时间内被非确定机解决的问题。通常它们的时间复杂度都是指数变量，如 O(2^n)等。这里有一个著名的问题一千禧难题之首。是说 P 问题是否等于 NP 问题，也即是否所有在非确定机上多项式可解的问题都能在确定机上用多项式时间求解。这表明用 NP 问题寻找多项式时间表示的算法很困难，或许最后的结论是 NP 问题根本就不是 P 问题。

• NP?=P 问题：目前已经证明所有 P 问题都是 NP 问题，那么反之 P—NP 吗?这就是所谓的“NP 问题”。目前 P 与 NP 是否等价是一个既没有证实也没有证伪的问题。但是大部分科学家猜想：找一个问题的解很困难，但验证一个解很容易(证比解易)，用公式表示就是 P≠NP。问题较难求解(P)但容易验证(NP)，这与我们的日常生活经验是相符的。

• NP-hard 问题：比 NP 问题更难的问题。

• NP 完全问题：计算机科学家将 NP 问题中最困难的称为 NPC 问题。NPC 问题有一个令人惊讶的性质，即如果一个 NPC 问题存在多项式时间算法，那么所有 NP 问题都可以在多项式时间内求解，即 P=NP 成立。这是因为每一个 NPC 问题都可以在多项式时间内转化成任何一个 NP 问题。只要任意一个 NPC 问题找到了一个多项式算法，那么所有 NP 问题都能用这个算法解决，也就解决了 NP=P 问题。

3、常见数据结构

• 数组：在计算机的连续的内存中存储相同类型的数据，支持随机访问

• 链表：利用计算机中零散的内存空间存储数据，查找数据的时间复杂度为 O(n)。其增删性能比数组好。

• 队列：一种先进先出的数据结构，也是占用连续的内存空间。

• 哈希表：基于数组变化而来的高效查询数据结构，查询的时间复杂度为 O(1)。

• 栈：一种先进后出的线性结构，只能在其一端操作。

案例：线程调用栈

4、非线性数据结构

1、树：树状图是一种数据结构，它是由 n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

2、二叉树：二叉树是 n 个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

待续。。。。