常见算法复杂度
常见算法复杂度，持续整理中
深度优先搜索(DFS)与广度优先搜索(BFS)
这两个算法可以用于图也可以用于树，用于树的情况往往会简单。
使用邻接矩阵存储图: O(n^2)
一共n个点，每个点都要访问一遍，每个点都要读取邻接矩阵获得子节点，需要n次，因此是n*n。
使用邻接表存储图：O(|n| + |e|)
注意：在树中，e = n - 1，因为只有根节点没有上面的边，其他点都有。所以使用邻接表或者tree的结构，时间复杂度是 O(n)
快速排序
采用Partition操作，复杂度是TreeHight * N，在树的每一层的parition操作中，都要有N次遍历操作。
最理想情况下，即每次partition都在中间位置划分，则树的高度是log(n)，最坏的情况则是树高趋于N。
LeetCode有一个关于快速排序的题目(SortList)，其中的一个测试用例包含大量的重复数字。而代码默认没有优化的话，这种情况下会很糟糕。
可以针对这种情况进行优化，在Partition的过程中将选定的PartitionValue的重复项都位于中间，返回两个partition点，如下面两端的5。然后剩下仅对左右两个部分进行运算即可。
|
|