架构师训练营 Week8 作业总结

用户头像
Up
关注
发布于: 2020 年 07 月 29 日

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

数据结构与算法

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)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。



待续。。。。



用户头像

Up

关注

代码,思考,架构,阅读,旅行。 2018.11.02 加入

一起来进步吧,持续学习的小白!

评论

发布
暂无评论
架构师训练营Week8作业总结