algorithm - 有助于比较具有相同时间复杂度的两种算法的因素

Question

我必须完成一项关于数字算法分析的研究。我需要一些关于该主题的专家意见。我知 Prop 有相同时间复杂度的两种算法会受到复杂度方程中常数(例如 alpha)的影响。具有较大 alpha 值的算法被认为比具有较小 alpha 的算法更差。复杂性的一个示例方程是F(n)=A(n^2+2n)

在时间复杂度相同的情况下，还有哪些其他因素会影响两种算法之间的比较？欢迎提出任何建议。

Answer 1

内存是另一个需要考虑的因素，例如，Mergesort 通常以相同的时间复杂度运行(尽管具有较低的常数因子)但空间是 Heapsort 的两倍(我说“通常”是因为就地 Mergesort 通常是 O (n^2))。计算最多 N 个素数的基本算法要求您存储最多 N 个素数，而 Sieve of Eratosthenes更省时，但要求您存储所有数字(不是所有素数)直到 N。Radix Sort在 O(n) 中运行(与在 O(n*log(n)) 中运行的 Heapsort/Mergesort/Quicksort 相反)，但几乎没有人使用 Radix Sort，因为它需要更多内存并且缓存性能差。另请注意，与等效的迭代算法相比，递归算法通常需要更多空间(以堆栈的形式)。

平均时间复杂度是另一个因素 - Bubblesort 和 Quicksort 在相同的最坏情况时间复杂度 (O(n^2)) 下运行，但 Bubblesort 的平均时间复杂度为 n^2，而 Quicksort 的平均时间复杂度为 n*log(n ).平衡二叉树中插入和查找的最差平均时间为n*log(n)，而哈希表中的插入和查找通常最差时间为O(n)且平均时间恒定。

有时算法具有相同的时间复杂度，但会使用更便宜的操作。例如，矩阵乘法的标准算法是O(n^3)；另一种算法(我忘了它的名字)以相同的时间复杂度运行，但它使用更少的乘法和更多的加法(加法比乘法便宜)。 (在这种情况下，常数因子会受到影响，因此它仍然是同类比较，但要注意同类算法比较。)

另一个考虑因素是并行化。基本矩阵乘法算法的运行时间复杂度与 block matrix multiplication algorith 相同。 ，但后者在并行运行时比前者效率更高。并行算法的一个子集还具有“无锁”特性，这意味着它们无需使用信号量或监视器或其他锁定结构即可实现同步；无锁算法的一个子集是“无等待”的，这意味着所有线程都可以保证取得进展。

缓存性能是另一个考虑因素——基本和 block 矩阵乘法算法使用大致相同的内存量，但 block 算法具有更好的缓存行为(更少的缓存未命中)

稳定性是许多数值算法中的一个因素。在求解常微分方程时，四阶Runge-Kutta方法收敛速度比隐式Euler方法快得多，但隐式Euler方法总是会收敛到解，而Runge-Kutta方法可能会出现不稳定(例如收敛到Infinity或NAN) .

许多算法要求所有数据驻留在主存中；相比之下，外部算法只需要在任何给定时间将一部分数据驻留在主内存中。例如，经典的 Mergesort 算法要求所有被排序的元素都驻留在内存中，而 Polyphase Mergesort 只要求元素的一个子集驻留在内存中，而其余元素驻留在硬盘驱动器或网络中。