一、算法时间复杂度为O（n!）的是什么算法

O(n!)的算法不称其为算法，它意味着这个问题尚未解决。n稍微大一点，就会耗尽CPU的算力。它比不断折纸、围棋盘上摆大米得到的数更大。这种“算法”是进行算法改进的对象。算法老师没有花力气说明这种算法的荒谬之处倒是个很不可思议的事情。n!是个很大的数，你可以用windows自带的计算器算一下1000的阶乘，看看它有几个0。超级计算机算到世界末日也无法算出规模为n=1000的问题。

我们现在看到的大多数算法，很多都是O(n!)之类问题的优化形式，应该感谢这些算法研制者。我相信现在一些公司，仍然会不断遭遇这类O(n!)的问题，需要足够好的数学家们来优化算法，进行简化。

如何理解快速排序的时间复杂度是O(nlogn)

快速排序的情况比较棘手，在最糟情况下，其运行时间为O(n2)。。 在平均情况下，快速排序的运行时间为O(nlogn)。

1、平均情况与最糟情况

快速排序的性能高度依赖于你选择的基准值。

最糟情况

假设你总是将名列前茅个元素用作基准值，且要处理的数组是有序的。 由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序。 注意，数组并没有被分成两半，相反，其中一个子数组始终为空，这导致调用栈非常长。

平均情况

假设你总是将中间的元素用作基准值，在这种情况下，调用栈如下。 调用栈短得多！ 因为你每次都将数组分成两半，所以不需要那么多递归调用。 你很快就到达 了基线条件，因此调用栈短得多。

名列前茅个示例展示的是最糟情况，而第二个示例展示的是优异情况。 在最糟情况下，栈长为 O(n)，而在优异情况下，栈长为O(log n)。

现在来看看栈的名列前茅层。 你将一个元素用作基准值，并将其他的元素划分到两个子数组中。 这涉及数组中的全部8个元素，因此该操作的时间为O(n)。 在调用栈的名列前茅层，涉及全部8个元素， 但实际上，在调用栈的每层都涉及O(n)个元素。

即便以不同的方式划分数组，每次也将涉及O(n)个元素。

在这个示例中，调用栈的高度为O(log n)，而每层需要的时间为O(n)。 因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。 这就是优异情况。 在最糟情况下，有O(n)层，因此该算法的运行时间为O(n) * O(n) = O(n2)。

2、归并排序和快速排序的时间复杂度都是 O(nlogn)，为什么说快速排序一般优于归并排序？

首先搬运stackOverflow的回答：Why is mergesort better for linked lists?

快速排序中效率的主要来源之一是参考位置，其中计算机硬件经过优化，因此访问彼此靠近的内存位置往往比访问分散在整个内存中的内存位置更快。快速排序中的分区步骤通常具有出色的局部性，因为它访问前面和后面附近的连续数组元素。因此，快速排序的性能往往比其他排序算法（如堆排序）好得多，即使它通常执行大致相同数量的比较和交换，因为在堆排序的情况下，访问更加分散。

此外，快速排序通常比其他排序算法快得多，因为它就地运行，无需创建任何辅助数组来保存临时值。与合并排序之类的东西相比，这可能是一个巨大的优势，因为分配和释放辅助数组所需的时间可能很明显。就地操作还可以提高快速排序的本地性。

使用链表时，这些优点都不一定适用。由于链表单元格通常分散在整个内存中，因此访问相邻的链表单元格没有局部性好处。因此，快速排序的巨大性能优势之一被吞噬了。同样，就地工作的好处不再适用，因为合并排序的链表算法不需要任何额外的辅助存储空间。

也就是说，快速排序在链表上仍然非常快。合并排序往往更快，因为它更均匀地将列表分成两半，并且每次迭代执行合并比执行分区步骤所做的工作更少。

快速排序中效率的主要来源之一是引用位置，在引用位置中，计算机硬件经过优化，因此访问彼此相邻的内存位置往往比访问分散在整个内存中的内存位置更快。 quicksort中的分区步骤通常具有很好的局部性，因为它访问前面和后面附近的连续数组元素。 因此，快速排序往往比其他排序算法（如heapsort）执行得更好，尽管它通常执行大致相同数量的比较和交换，因为在heapsort的情况下，访问更加分散。

此外，quicksort通常比其他排序算法快得多，因为它在原地运行，而不需要创建任何辅助数组来保存临时值。 与merge sort相比，这是一个巨大的优势，因为分配和释放辅助数组所需的时间是显而易见的。 就地操作也提高了quicksort的位置。

使用链表时，这两个优点都不一定适用。 由于链表单元通常分散在整个内存中，因此访问相邻的链表单元没有额外的局部性好处。 因此，quicksort的一个巨大的性能优势被消耗殆尽。 类似地，就地工作的好处不再适用，因为merge sort的链表算法不需要任何额外的辅助存储空间。

也就是说，快速排序在链接列表中仍然非常快。 合并排序往往更快，因为它更均匀地将列表分成两半，并且每次执行合并所做的工作比执行分区步骤所做的工作更少。

延伸阅读：

二、无锁数据结构的好处

主要原因： 将并发最大化。

使用基于锁的容器， 会让线程阻塞或等待； 互斥锁削弱了结构的并发性。 在无锁数据结构中， 某些线程可以逐步执行。 在无等待数据结构中， 无论其他线程当时在做什么， 每一个线程都可以转发进度。

健壮性：

如果线程在持有锁的同时死亡，那么该数据结构将永远被破坏。但是，如果线程在对无锁数据结构的操作中途中途死亡，则除了该线程的数据外，什么都不会丢失。其他线程可以正常进行。

死锁活锁问题：

死锁问题不会困扰无锁数据结构; 无等待的代码不会被活锁所困扰,因其操作执行步骤是有上限的。

上一篇

数据结构到底是什么?

下一篇

制作线路图哪款软件好用?