基本概念 递归可以层次可以通过tree的形式展现。 比如下面的递归： 时间复杂度:就是总的树的节点s数。如果每一次层嵌套都包涵2层平行的call，那时间复杂度就是O(2^N).如果有四层，那么就是O（4^N). 空间复杂度:就是总的树的深度。在这里就是N 深度优先算法(DFS: Depth First Search) 深度优先算法是一个递归调用。对于图的深度优先，我们有Vertices和Edge的数量，分别用V和E来表示。 时间复杂度：因为是图，所以在递归的时候每一次层有多少节点是不知道的，所以没办法按照2^n的普遍算法来算。但是换一个思路就是无论如何每条边都至少需要走一遍。时间复杂度就是总的边的数量，每条边会被访问两次，一次是遍历，一次是会退。O(E). 空间复杂: 如果所有的Vertices都是相连的，那么就会有V层深度的书。那空间复杂度就是O(V) 广度优先算法(BFS: Breadth First Search) todo 时间复杂度: O(V+E). 这里不是说O(E)比O（V+E）好。其实O(E)是O(2E).因为复杂度计算忽略常量，这里容易引起误解。 空间复杂: O(V) Reference: https://stackoverflow.com/questions/43298938/space-complexity-of-recursive-functionhttps://zhuanlan.zhihu.com/p/95081559#:~:text=%E5%9C%A8%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95,%E5%BA%A6%E4%B8%BAO(V)%E3%80%82

其实不同数据结构的性能差别还是很明显的，只是在实际使用中这种差别会被网络等各种开销所掩盖。所以这里看到的1000倍以上的差别可能在实际场景中并不那么明显。 下面写写出结果： 运行环境时m1 CPU的macbook mini。可以看到插入1000个int到数组是0.017ms, ArrayList是0.584ms, LinkedList是0.379ms，HashSet是5ms,LinkedHashSet是2ms。最好和最差之间相差500倍。 但是如果要在网络传输这么1000个integer对象，可能直接就是几十毫秒的花销了，存储的时间根据不同介质也要几毫秒不等。而且通常如果需要存储的话肯定也需要网络开销，本地存储的概率很低。 但是这些基础的性能开销上的差别在大数据处理的时候应该还是能显现出差别的。最慢的5ms 1k数据，如果数量级到1million的话，那么就是5s，1billion的话就是1个多小时。如果用int的话，那就是10s。1个多小时 VS 10s 还是很可观的差距。只是不知道把1billion的数据load到内存需要多久😂 在实际的项目中其实也从来没有遇到过这种内存计算开销导致的性能瓶颈。如果以后什么时候遇到了，我再回来update这里。。

很久没有真的写程序，一些基本的Utils的使用也淡忘了。这里总结一下: 数组 数组转化成List List转化为数组 排序数组 排序List 打印一维数组 打印多于一维数组 打印List 答应list里面含有array MAP Merge Print a map 其他 boolean的值只能是true，false，而不能是0，1. char是用单引号: char abc=’a’;

最开始其实想说一下Leedcode提供的实现的代码质量其实真的一般，如果有人面试的时候用实例代码的风格，我估计算法写的再好也没太大用。最简单的变量命名。尽然有这样的代码: Map<Integer, Integer> map = new HashMap<>(); 每定义一个变量都要花时间至少稍微想一个变量命名，这是一个最基本的习惯。写出用map作为变量名的人绝对不是有经验的好工程师应该做的事情。 好了，言归正传。 Two Sum可以算是算法题里面最简单的之一了。下面是题目和LeetCode Premium给出的一个SolutionO(N) Solution. 题目: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. 下面是采用Two Pass的 O(N)时间复杂度的解答: To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array…

最近看一些算法题，各种时间复杂度，空间复杂度充斥脑海。O(N), O(N^2), O(NLogN)。这里拿LRU(Least Recently Used)算法来举一个例子算法和实际的差别。 这个是Leetcode里面的算法: https://leetcode.com/problems/lru-cache/. 没有兴趣的人其实也不用看，基本上就是设计一个LRU算法，保证读取和插入的时间复杂度都是O(N). 代码基本上也就100行左右，貌似很简单。但是如果看Redis的文档我们会发现这段话： https://redis.io/topics/lru-cache Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys. 既然算法这么简单为什么Redis的默认实现不去做严格的LRU呢？其实原因很简单，为了节省空间。在传统的时间和空间复杂度里面，所有的非指数级的增长都被归纳成一个结果。比如说O(N) 和 O(2n)，或者更夸张的O(100N)或者更多。这在实际中能是一样的？使用double的空间，花费double的时间，再怎么说也不一样的。