数据结构与算法-开篇

从今天开始，就要开始进行数据结构与算法的训练了，计划每周两篇小短文，主要讲述自己解题思路，看的资料的总结，深入理解后自己的感悟。

为什么要学习数据结构与算法？

一言记之曰：换个用高性能代码解决问题的思路来解决问题。学习数据结构与算法，其实是为了在解决日常研发问题时，能有时间复杂度、空间复杂度意识，写出高质量代码，能够设计基础的架构，提升编程技能，训练逻辑思维等。而且在日常工作中，看待问题能够有新的认知。

为什么算法与数据结构一直都在一起？

算法与数据结构相辅相成，数据结构为算法服务，算法作用在特定的数据结构之上。两者不能割离。就像深度与广度优先算法，就要建立在图或者树这种数据结构之上，就像最简单的数组，数据因为自身有一整块的存储空间，所以具有按下标随机访问的特点，二分查找算法就需要用到数组存储数据，链表就无法实现了。 计算机最大的作用就是计算，计算就需要用到算法，而算法就是建立在基本的存储结构也就是基本的数据结构之上。

复杂度分析很重要么？

数据结构与算法解决的是问题，而复杂度分析就是对这个解决问题的思路的考量。如果不去考量一个思路，不去分析这个解决问题的思路，那么就像学武功只懂套路，不懂心法，达不到最高境界。空间复杂度O(n)也就是计算机资源的消耗，时间复杂度T(n)也即算法的执行效率，这些分析思路，对能否多快好省的解决问题起到重要的作用。

复杂度的量级初步了解

结合leetcode-数的相加 浅析复杂度

A. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order. 这道题的解题思路有很多种，我就举两种来看例如

1.把数组先排序，然后逐个遍历计算，毕竟每次把target减去第一个数之后，遍历没有对应的差值，就可以继续往后用target减去第二次遍历的第一个数，如此循环遍历，但是这种时间复杂度，如果按照快排来排序数组来计算最优时间复杂度就是O(nlogn)，但是当数据倒序，而需要顺序排序，那么复杂度就是O(n然后是不断重复遍历，也就是如果有n个数，也就是要做n(n-1)+(n-1)(n-2)...次，那么最后的时间复杂度就是O(n2)+O(n^2)。虽然说，空间复杂度不高，毕竟只需要做数据交换，但是毕竟时间复杂度高了,两个复杂度加起来就相当高了。代码过于简单，这里就不演示了。2.以下介绍一种空间复杂度和时间复杂度都很少的方式，先看代码

func twoSum(nums []int, target int) []int { record := make(map[int]int) ret := make([]int,2) for i := range nums{ if _,ok := record[nums[i]];ok{ ret[0] = record[nums[i]] ret[1] = i break } record[target-nums[i]] = i } return ret}

为什么说这时间复杂度很少，他不需要排序，只需要遍历一遍就能找到两数之和的下标值。那么空间复杂度是多少？考虑到返回只需要两个下标，这里只申请了两个长度的切片ret，而record是一个map，单纯记录了target与nums[i]的差值的下标，也就是如果nums所有的数据都需要遍历一遍，那么也只有O(n)的空间复杂度，有的时候还不需要。 提及一下，上面的题目用到了一个数据结构叫Map，他是一种哈希表，对于这种数据结构以后的题目都会常常有用到，在这里我简单的解析下，哈希表也叫散列表，散列表是数组的一种扩展，使用一种键值对的方式，使用键通过固定的哈希函数找到对应的值。显然，哈希表对重要的是哈希函数，针对哈希函数的设计，包括哈希冲突，装载因子等。后续会就哈希专门开一篇讲解，这里就不详细展开讲。

复杂度该如何分析？

其实复杂度的分析是需要结合题目来讲解会比较好，在后面的篇章中，结合算法题会持续将上面的量级的图拿出来，作为分析时的对照点，这样读者就能结合算法题不断练习，一眼看出程序的复杂度。复杂度分析没有捷径，只有不断地练习。