对于同一任务，您可能选择使用 Θ(n log n) 时间算法而不是 Θ(n) 时间算法的原因
Reasons you might choose to use a Θ(n log n) time algorithm over a Θ(n) time algorithm for the same task
这个问题出现在家庭作业中。我不明白为什么？似乎您总是希望选择产生最佳 运行 时间的算法。
Big O 和 Big Theta 表示法仅表示对于任意大的输入大小，性能趋于某种极限。例如，函数 99999999n 是 O(n)，而函数 (1/9999999999)n^2 是 O(n^2)。但是，对于任何合理大小（不是无限大）的输入，O(n^2) 函数显然可能更快。
换句话说，如果您可以对输入数据做出假设，在某些情况下通常较差的算法可能会表现更好。
上述概念的一个现实世界示例是排序 - 如果数组已经排序（冒泡排序），则有一些算法可以在 O(n) 时间内执行。如果您知道您的许多数组已经排序，您可能会出于这个原因选择使用冒泡排序而不是合并排序。
您可能不想使用更省时的算法的另一个极端情况是 space 效率。也许您正在使用非常小的 RAM 的嵌入式设备进行编程。您宁愿使用更少的内存并浪费更多的时间，也不愿尽可能地节省时间。
这个问题出现在家庭作业中。我不明白为什么？似乎您总是希望选择产生最佳 运行 时间的算法。
Big O 和 Big Theta 表示法仅表示对于任意大的输入大小，性能趋于某种极限。例如，函数 99999999n 是 O(n)，而函数 (1/9999999999)n^2 是 O(n^2)。但是，对于任何合理大小（不是无限大）的输入，O(n^2) 函数显然可能更快。
换句话说，如果您可以对输入数据做出假设，在某些情况下通常较差的算法可能会表现更好。
上述概念的一个现实世界示例是排序 - 如果数组已经排序（冒泡排序），则有一些算法可以在 O(n) 时间内执行。如果您知道您的许多数组已经排序，您可能会出于这个原因选择使用冒泡排序而不是合并排序。
您可能不想使用更省时的算法的另一个极端情况是 space 效率。也许您正在使用非常小的 RAM 的嵌入式设备进行编程。您宁愿使用更少的内存并浪费更多的时间，也不愿尽可能地节省时间。