0

I have to complete a study on analysis of digital algorithms. I need some expert ideas on the topic. I understand that two algorithms having the same time complexity are affected by the constant, say alpha, in there complexity equations. The algorithm with a greater value of alpha is considered poorer to an algorithm with a smaller alpha. An example equation for the complexity would be F(n)=A(n^2+2n)

What other factors govern the comparison between two algorithms in case they are of the same time complexity? Any suggestions would be most welcome.

4

1 回答 1

2

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

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

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

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

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

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

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

于 2013-04-21T16:11:04.940 回答