架构师训练营 第八周 个人感想

0 期 3 班 4 组 杨娴艳



本周的学习涉及到的点包括数据结构、算法、网络和数据库性能，以下将针对部分知识加上部分参考资料的补充和个人的理解进行梳理。

时间复杂度和空间复杂度

衡量代码的好坏，包括两个非常重要的指标：运行时间和占用时间。

时间复杂度

由于运行环境和输入规模的影响，代码的绝对执行时间是无法估计的，但我们可以预估出代码的基本操作执行次数。

维基百科对时间复杂度的定义为：

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

智慧老师的课件定义为：并不是计算程序具体运行的时间，而是算法执行语句的次数。相对来说，智慧老师的总结更加简单易懂。



推导出时间复杂度有以下几个原则：

1. 如果运行时间是常数量级，用常数1表示；

2. 只保留时间函数中的最高阶项；

3. 如果最高阶项存在，则省去最高阶项前面的系数。



举例说明：

1）T（n） = 3n 

最高阶项为3n，省去系数3，转化的时间复杂度为： O（n）

2）T（n） = 5logn 

最高阶项为5logn，省去系数5，转化的时间复杂度为：O（logn）

3）T（n） = 2

只有常数量级，转化的时间复杂度为：O（1）

4）T（n） = 0.5n^2 + 0.5n

最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：O（n^2）

空间复杂度

维基百科对空间复杂度的定义为：

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指针，一般来说，空间复杂度越小，算法越好。我们假设有一个图灵机来解决某一类语言的某一问题，设有X个字属于这个问题，把X放入这个图灵机的输入端，这个图灵机为解决此问题所需要的工作带格子数总和称为空间。

智慧老师的课件定义为：一个算法在运行过程中临时占用存储空间大小的量度。

总结

在进行本周的算法练习中，需要找到两个长短链表的交叉节点，当时我在第一版算法中自然而然就是运用了遍历两个链表进行查找的思路，进行了思考后再进行了第二版的算法改进，将复杂度从O(n*m)改进为O(n)。

数据结构

数组

维基百科对数组的定义为：

在计算机科学中，数组数据结构，简称数组，是由相同类型的元素的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引可以计算出该元素对应的存储地址。



1、创建数组必须要内存中一块连续的空间。

2、数组中必须存放相同的数据类型。

3、随机快速读写是数组的一个重要特性，根据数组的下标访问数据，时间复杂度为O(1)。

链表

维基百科对链表的定义为：

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。



1、链表可以使用零散的内存空间存储数据。

2、链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

3、要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是O(N)。

总结

1、数组的查询效率比链表性能好；

2、链表的增删数据的性能比数组要好。

Hash表

维基百科对Hash表的定义为：

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

栈

维基百科对栈的定义为：

堆栈又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端进行加入数据和移除数据的运算。因而按照后进先出的原理运作。

队列

维基百科对队列的定义为：

队列，计算机科学中的一种抽象资料型别，是先进先出的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端进行插入操作，在前端进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

树

维基百科对树的定义为：

在图论中，树是一种无向图，其中任意两个顶点间存在唯一一条路径。或者说，只要没有回路的连通图就是树。森林是指互相不交并树的集合。树图广泛应用于计算机科学的数据结构中，比如二叉查找树，堆，Trie树以及数据压缩中的霍夫曼树等等。

总结

数据结构和算法是密切相关的，数据结构和编程设计也是密切相关的，在大学里面专门学习的数据结构这门课，是因为它是介于数学、计算机硬件和软件三者之间一门核心学科。了解了以上的抽象数据类型描述的数据结构，在设计软件的时候可以提高软件的整体性能和利用率，也可以将数据类型的特殊结构运用于各类场景的算法中，如：通过队列搜索最短路径等。

算法

本周的算法题让我跃跃欲试可以每周都做一道类似这样的题目，不仅让自己的思维更加敏捷和开阔，也在分析过程中对数据结构的基础知识一遍遍的进行刷新，在Java开发过程中，有很多优秀的框架，如Apache Common，Google Guava 都不仅仅是我们该学会怎么使用的，我们也应该多阅读相关源码，学习里面的精髓。

网络通信协议

说实话，这一块即便在大学都一直是自己的弱项，因为网络相关的知识太抽象了，同时涉及到的一些如子网掩码等的计算又相对较为复杂，作为一名研发人员在两年前没有接触Devops和容器化技术之前是基本不怎么接触到相关知识的，但随着后续接触到容器化技术、公有云的部署和运维，互联网分布式架构的学习和中间件的学习等都对这块有或多或少的关联，后续在工作中还是需要不断加强这方面的学习，做到心中有数。



这周还有很多的知识点，就不一一累述了，有很多没有掌握，特别是涉及算法的，但有机会定定心心的把老师提出的作业研究思考后做完，然后找时间把课程再复盘学习两遍至少是现在可以做到的，不要畏难，继续前行，相信未来的我们会感谢现在努力的自己。