O(n log n) 时间和 O(1) space 复杂度与 O(n) 时间和 O(n) space 复杂度的算法
Algorithm with O(n log n) time and O(1) space complexity vs O(n) time and O(n) space complexity
我很想知道哪种算法更好:
- 具有 O(n log n) 时间和 O(1) space 复杂度的算法
- 具有 O(n) 时间和 O(n) space 复杂度的算法
大多数在 O(n long n) 时间内解决的算法和常量 space 可以在 O(n) 时间内解决，只需根据 space 支付惩罚。哪种算法更好？
我该如何决定这两个参数？
示例：数组对和
- 可以通过排序在O(n logn)时间内解决
- 可以在 O(n) 时间内使用哈希映射解决，但 O(n) space
在没有实际测试任何东西的情况下（一个冒险的举动！），我将声称 O(n log n)-time，O(1)-space 算法可能比 O (n)-时间，O(n)-space算法，但可能仍然不是最优算法。
首先，让我们从高层次的角度来讨论这个问题，忽略您所描述的算法的特定细节。要记住的一个细节是，虽然 O(n) 时间算法比 O(n log n) 时间算法渐近地快，但它们只快一个对数因子。请记住，宇宙中的原子数约为 1080（感谢物理学！），宇宙中原子数的 2 进制对数约为 240。来自从实用的角度来看，这意味着您可以将额外的 O(log n) 因子视为一个常数。因此，要确定 O(n log n) 算法在特定输入上是否比 O(n) 算法更快或更慢，您需要更多地了解大 O 表示法隐藏了哪些常量。例如，对于适合宇宙的任何 n，在时间 600n 中运行的算法将比在时间 2n log n 中运行的算法慢。因此，就挂钟性能而言，要评估哪种算法更快，您可能需要对算法进行一些分析以查看哪种算法更快。
然后是缓存和引用位置的影响。计算机内存中有大量缓存，这些缓存针对读取和写入彼此相邻的情况进行了优化。缓存未命中的代价可能是巨大的——比命中慢数百或数千倍——所以你想尽量减少这种情况。如果算法使用 O(n) 内存，那么当 n 变大时，您需要开始担心内存访问的密集程度。如果它们分散开来，那么缓存未命中的成本可能会开始快速增加，从而显着提高隐藏在时间复杂度的大 O 表示法中的系数。如果它们是更连续的，那么你可能不需要太担心这个。
您还需要注意可用内存总量。如果您的系统上有 8GB 的 RAM 并获得一个包含 10 亿个 32 位整数的数组，那么如果您需要 O(n) 辅助 space 甚至一个合理的常数，您将无法将你的辅助内存放入主内存，它将开始被 OS 调出页面，真正杀死你的运行时间。
最后是随机性问题。基于散列的算法具有 预期的 快速运行时间，但如果您得到一个错误的散列函数，算法可能会变慢。生成良好的随机位很难，因此大多数哈希 table 只使用 "reasonably good" 哈希函数，冒着最坏情况输入的风险，这将使算法的性能下降。
那么这些担忧在实践中是如何发挥作用的呢？好吧，让我们看看算法。 O(n)-time，O(n)-space 算法通过构建数组中所有元素的散列 table 来工作，以便您可以轻松地检查给定元素是否存在于数组中数组，然后扫描数组并查看是否有一对加起来等于总数。考虑到上述因素，让我们考虑一下这个算法是如何工作的。
内存使用为 O(n)，并且由于散列的工作方式，对散列 table 的访问不太可能是连续的（理想的散列 table 会有相当多的随机访问模式）。这意味着您将有很多缓存未命中。
高内存使用意味着对于大输入，你不得不担心内存被分页进出，加剧了上述问题。
由于以上两个因素，隐藏在O(n) 运行时中的常数项很可能比看起来要高得多。
哈希在最坏情况下效率不高，因此可能存在导致性能显着下降的输入。
现在，考虑 O(n log n) 时间，O(1) space 算法，该算法通过执行就地数组排序（例如，堆排序），然后从左边和右边，看看你是否能找到一对总和达到目标的。此过程中的第二步具有出色的引用局部性——实际上所有数组访问都是相邻的——而且几乎所有你将要获得的缓存未命中都将出现在排序步骤中。这将增加隐藏在大 O 符号中的常数因子。然而，该算法没有退化输入，其低内存占用可能意味着引用的局部性将优于散列 table 方法。因此，如果我不得不猜测，我会把钱花在这个算法上。
...好吧，实际上，我会把钱花在第三种算法上：O(n log n)-时间，O(log n)-space 算法，基本上就是上面的算法，但使用 introsort 而不是堆排序。 Introsort 是一种 O(n log n)-time，O(log n)-space 算法，它使用随机快速排序主要对数组进行排序，如果快速排序看起来即将退化，则切换到堆排序，并执行最后的插入排序通过清理所有内容。 Quicksort 具有惊人的引用局部性 - 这就是它如此之快的原因 - 并且插入排序在小输入上更快，所以这是一个很好的折衷方案。另外，O(log n) 额外的内存基本上没什么 - 请记住，在实践中，log n 最多为 240。该算法具有您可以获得的最佳参考位置，给出了 O( n log n) 项，因此它在实践中可能会优于其他算法。
当然，我也必须对这个答案进行限定。我在上面所做的分析假设我们正在讨论算法的相当大的输入。如果您只查看少量输入，那么整个分析就会结束 window，因为我考虑的影响不会开始显示。在这种情况下，最好的选择就是分析这些方法并查看哪种方法最有效。从那里，您可能能够构建一种 "hybrid" 方法，在这种方法中，您对一个大小范围内的输入使用一种算法，对不同大小范围内的输入使用不同的算法。很有可能这会提供一种击败任何一种方法的方法。
也就是说，用 Don Knuth 的话说，"beware of the above analysis - I have merely proved it correct, not actually tried it." 最好的选择是分析所有内容并查看其工作原理。我没有这样做的原因是通过分析要注意哪些因素，并强调比较这两种算法的纯大 O 分析的弱点。我希望实践能证明这一点！如果没有，我很想看看我哪里做错了。 :-)
根据经验：
- 如果您绝对负担不起 space，请前往 O(1) space 路线。
- 当随机访问不可避免时，走O(n) space 路线。 (通常比较简单，时间常数也较小。)
- 当随机访问很慢时（例如寻道时间），走 O(1) space 路线。 （您通常可以找到一种缓存一致的方法。）
- 否则，随机访问速度很快——走 O(n) space 路线。 (通常时间常数越小越简单。)
请注意，如果问题出在比瓶颈存储更快的内存中，通常随机访问是 "fast"。 （例如，如果磁盘是瓶颈，主内存对于随机访问足够快 --- 如果主内存是瓶颈，CPU 缓存对于随机访问足够快）
使用您的特定算法示例 Array Pair Sum，O(n) 时间 O(n) space 的哈希版本会更快。这是一个小 JavaScript 基准测试，您可以使用 http://jsfiddle.net/bbxb0bt4/1/
我在基准测试中使用了两种不同的排序算法，快速排序和基数排序。在这种情况下，基数排序（32 位整数数组）是理想的排序算法，甚至它几乎无法与单遍散列版本竞争。
如果你想要一些关于编程的一般性意见：
- 优先使用O(N)时间和O(N) space算法，因为实现会更简单，这意味着更容易维护和调试。
function apsHash(arr, x) {
var hash = new Set();
for(var i = 0; i < arr.length; i++) {
if(hash.has(x - arr[i])) {
return [arr[i], x - arr[i]];
}
hash.add(arr[i]);
}
return [NaN, NaN];
}
function apsSortQS(arr, x) {
arr = quickSortIP(arr);
var l = 0;
var r = arr.length - 1;
while(l < r) {
if(arr[l] + arr[r] === x) {
return [arr[l], arr[r]];
} else if(arr[l] + arr[r] < x) {
l++;
} else {
r--;
}
}
return [NaN, NaN];
}
您总是可以用 O(n) 时间 O(n) space 替换 O(n lg n) 时间 O(1) space 算法，这是不正确的。这真的取决于问题，并且有许多不同的算法，它们对时间和 space 具有不同的复杂性，而不仅仅是线性或线性对数（例如 n log n）。
请注意，O(1) space 有时意味着（如您的示例）您需要修改输入数组。所以这实际上意味着你确实需要 O(n) space，但你可以以某种方式使用输入数组作为你的 space（与真正只使用常量 space 的情况相比）。更改输入数组并不总是可能或允许的。
至于在具有不同时间和space特性的不同算法之间进行选择，这取决于您的优先级。通常，时间是最重要的，所以如果你有足够的内存，你会选择最快的算法（记住这个内存只是在算法 运行 时临时使用）。如果你真的没有所需的space，那么你会选择一个更慢的算法，它需要更少的space。
因此，一般的经验法则是选择最快的算法（不仅仅是通过渐近复杂度，而是根据您的常规工作负载的实际现实世界最快执行时间）可以适应其 space要求。
要比较两种算法，首先应该明确我们比较的是什么。
如果我们的优先级是 space，则 T(n)=O(n log n) & S(n)=O(1) 的算法更好。
在一般情况下，第二个 T(n)=O(n) & S(n)=O(n) 更好，因为 space 可以补偿但时间不能。
选择算法方法时应牢记三点。
- 在最坏的情况下，应用程序 运行 顺利运行的时间。
- Space 可用性取决于程序将 运行 在的环境类型。
- 所创建函数的可重用性。
鉴于这三点，我们可以决定哪种方法适合我们的应用。
如果我有有限的 space 和合理的数据提供给它，那么条件 2 将发挥主要作用。这里，我们可以用O(nlogn)检查平滑度，并尝试优化代码并重视条件3。
（例如，Array Pair Sum 中使用的排序算法可以在我的代码的其他地方重复使用。）
如果我有足够的 space，那么按时即兴创作将是主要问题。在这里，而不是可重用性，人们将专注于编写省时的程序。
假设您的假设是正确的。
鉴于在现实生活中不存在无限资源这一事实，并且在实施解决方案时，您将尽最大努力实施最可靠的解决方案（一种不会因为您消耗了所有允许的内存而中断的解决方案），我会很明智然后一起去：
Algorithm with O(n log n) time and O(1) space complexity
即使你有大量的内存，并且你确定你永远不会耗尽你的内存，使用消耗大量内存的解决方案可能会导致很多问题（I/O read/write 速度，在发生故障时备份数据）而且我想没有人喜欢在启动时使用 2Go 内存并且随着时间的推移不断增长的应用程序，就好像存在内存泄漏一样。
我想最好是写一个测试，
实际算法，数据量（n），
和内存使用模式将很重要。
此处是 model 的简单尝试；
random() 函数调用和 mod 时间复杂度的操作，
space 复杂度的随机内存访问 (read/write)。
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <math.h>
int test_count = 10;
int* test (long time_cost, long mem_cost){
// memory allocation cost is also included
int* mem = malloc(sizeof(int) * mem_cost);
long i;
for (i = 0; i < time_cost; i++){
//random memory access, read and write operations.
*(mem + (random() % mem_cost)) = *(mem + (random() % mem_cost));
}
return mem;
}
int main(int argc, char** argv){
if (argc != 2) {
fprintf(stderr,"wrong argument count %d \nusage: complexity n", argc);
return -1;
}
long n = atol(argv[1]);
int *mem1, *mem2;
clock_t start,stop;
long long sum1 = 0;
long long sum2 = 0;
int i = 0;
for (i; i < test_count; i++){
start = clock();
mem1 = test(n * log(n), 1);
stop = clock();
free(mem1);
sum1 += (stop - start);
start = clock();
mem2 = test(n , n);
stop = clock();
free(mem2);
sum2 += (stop - start);
}
fprintf(stdout, "%lld \t", sum1);
fprintf(stdout, "%lld \n", sum2);
return 0;
}
禁用优化；
gcc -o complexity -O0 -lm complexity.c
测试；
for ((i = 1000; i < 10000000; i *= 2)); do ./complexity $i; done | awk -e '{print / }'
我得到的结果；
7.96269
7.86233
8.54565
8.93554
9.63891
10.2098
10.596
10.9249
10.8096
10.9078
8.08227
6.63285
5.63355
5.45705
在某些时候 O(n) 在我的机器上做得更好,
一段时间后，O(n*logn) 变得更好，（我没有使用交换）。
我很想知道哪种算法更好:
- 具有 O(n log n) 时间和 O(1) space 复杂度的算法
- 具有 O(n) 时间和 O(n) space 复杂度的算法
大多数在 O(n long n) 时间内解决的算法和常量 space 可以在 O(n) 时间内解决，只需根据 space 支付惩罚。哪种算法更好？ 我该如何决定这两个参数？
示例：数组对和
- 可以通过排序在O(n logn)时间内解决
- 可以在 O(n) 时间内使用哈希映射解决，但 O(n) space
在没有实际测试任何东西的情况下（一个冒险的举动！），我将声称 O(n log n)-time，O(1)-space 算法可能比 O (n)-时间，O(n)-space算法，但可能仍然不是最优算法。
首先，让我们从高层次的角度来讨论这个问题，忽略您所描述的算法的特定细节。要记住的一个细节是，虽然 O(n) 时间算法比 O(n log n) 时间算法渐近地快，但它们只快一个对数因子。请记住，宇宙中的原子数约为 1080（感谢物理学！），宇宙中原子数的 2 进制对数约为 240。来自从实用的角度来看，这意味着您可以将额外的 O(log n) 因子视为一个常数。因此，要确定 O(n log n) 算法在特定输入上是否比 O(n) 算法更快或更慢，您需要更多地了解大 O 表示法隐藏了哪些常量。例如，对于适合宇宙的任何 n，在时间 600n 中运行的算法将比在时间 2n log n 中运行的算法慢。因此，就挂钟性能而言，要评估哪种算法更快，您可能需要对算法进行一些分析以查看哪种算法更快。
然后是缓存和引用位置的影响。计算机内存中有大量缓存，这些缓存针对读取和写入彼此相邻的情况进行了优化。缓存未命中的代价可能是巨大的——比命中慢数百或数千倍——所以你想尽量减少这种情况。如果算法使用 O(n) 内存，那么当 n 变大时，您需要开始担心内存访问的密集程度。如果它们分散开来，那么缓存未命中的成本可能会开始快速增加，从而显着提高隐藏在时间复杂度的大 O 表示法中的系数。如果它们是更连续的，那么你可能不需要太担心这个。
您还需要注意可用内存总量。如果您的系统上有 8GB 的 RAM 并获得一个包含 10 亿个 32 位整数的数组，那么如果您需要 O(n) 辅助 space 甚至一个合理的常数，您将无法将你的辅助内存放入主内存，它将开始被 OS 调出页面，真正杀死你的运行时间。
最后是随机性问题。基于散列的算法具有 预期的 快速运行时间，但如果您得到一个错误的散列函数，算法可能会变慢。生成良好的随机位很难，因此大多数哈希 table 只使用 "reasonably good" 哈希函数，冒着最坏情况输入的风险，这将使算法的性能下降。
那么这些担忧在实践中是如何发挥作用的呢？好吧，让我们看看算法。 O(n)-time，O(n)-space 算法通过构建数组中所有元素的散列 table 来工作，以便您可以轻松地检查给定元素是否存在于数组中数组，然后扫描数组并查看是否有一对加起来等于总数。考虑到上述因素，让我们考虑一下这个算法是如何工作的。
内存使用为 O(n)，并且由于散列的工作方式，对散列 table 的访问不太可能是连续的（理想的散列 table 会有相当多的随机访问模式）。这意味着您将有很多缓存未命中。
高内存使用意味着对于大输入，你不得不担心内存被分页进出，加剧了上述问题。
由于以上两个因素，隐藏在O(n) 运行时中的常数项很可能比看起来要高得多。
哈希在最坏情况下效率不高，因此可能存在导致性能显着下降的输入。
现在，考虑 O(n log n) 时间，O(1) space 算法，该算法通过执行就地数组排序（例如，堆排序），然后从左边和右边，看看你是否能找到一对总和达到目标的。此过程中的第二步具有出色的引用局部性——实际上所有数组访问都是相邻的——而且几乎所有你将要获得的缓存未命中都将出现在排序步骤中。这将增加隐藏在大 O 符号中的常数因子。然而，该算法没有退化输入，其低内存占用可能意味着引用的局部性将优于散列 table 方法。因此，如果我不得不猜测，我会把钱花在这个算法上。
...好吧，实际上，我会把钱花在第三种算法上：O(n log n)-时间，O(log n)-space 算法，基本上就是上面的算法，但使用 introsort 而不是堆排序。 Introsort 是一种 O(n log n)-time，O(log n)-space 算法，它使用随机快速排序主要对数组进行排序，如果快速排序看起来即将退化，则切换到堆排序，并执行最后的插入排序通过清理所有内容。 Quicksort 具有惊人的引用局部性 - 这就是它如此之快的原因 - 并且插入排序在小输入上更快，所以这是一个很好的折衷方案。另外，O(log n) 额外的内存基本上没什么 - 请记住，在实践中，log n 最多为 240。该算法具有您可以获得的最佳参考位置，给出了 O( n log n) 项，因此它在实践中可能会优于其他算法。
当然，我也必须对这个答案进行限定。我在上面所做的分析假设我们正在讨论算法的相当大的输入。如果您只查看少量输入，那么整个分析就会结束 window，因为我考虑的影响不会开始显示。在这种情况下，最好的选择就是分析这些方法并查看哪种方法最有效。从那里，您可能能够构建一种 "hybrid" 方法，在这种方法中，您对一个大小范围内的输入使用一种算法，对不同大小范围内的输入使用不同的算法。很有可能这会提供一种击败任何一种方法的方法。
也就是说，用 Don Knuth 的话说，"beware of the above analysis - I have merely proved it correct, not actually tried it." 最好的选择是分析所有内容并查看其工作原理。我没有这样做的原因是通过分析要注意哪些因素，并强调比较这两种算法的纯大 O 分析的弱点。我希望实践能证明这一点！如果没有，我很想看看我哪里做错了。 :-)
根据经验：
- 如果您绝对负担不起 space，请前往 O(1) space 路线。
- 当随机访问不可避免时，走O(n) space 路线。 (通常比较简单，时间常数也较小。)
- 当随机访问很慢时（例如寻道时间），走 O(1) space 路线。 （您通常可以找到一种缓存一致的方法。）
- 否则，随机访问速度很快——走 O(n) space 路线。 (通常时间常数越小越简单。)
请注意，如果问题出在比瓶颈存储更快的内存中，通常随机访问是 "fast"。 （例如，如果磁盘是瓶颈，主内存对于随机访问足够快 --- 如果主内存是瓶颈，CPU 缓存对于随机访问足够快）
使用您的特定算法示例 Array Pair Sum，O(n) 时间 O(n) space 的哈希版本会更快。这是一个小 JavaScript 基准测试，您可以使用 http://jsfiddle.net/bbxb0bt4/1/
我在基准测试中使用了两种不同的排序算法，快速排序和基数排序。在这种情况下，基数排序（32 位整数数组）是理想的排序算法，甚至它几乎无法与单遍散列版本竞争。
如果你想要一些关于编程的一般性意见：
- 优先使用O(N)时间和O(N) space算法，因为实现会更简单，这意味着更容易维护和调试。
function apsHash(arr, x) {
var hash = new Set();
for(var i = 0; i < arr.length; i++) {
if(hash.has(x - arr[i])) {
return [arr[i], x - arr[i]];
}
hash.add(arr[i]);
}
return [NaN, NaN];
}
function apsSortQS(arr, x) {
arr = quickSortIP(arr);
var l = 0;
var r = arr.length - 1;
while(l < r) {
if(arr[l] + arr[r] === x) {
return [arr[l], arr[r]];
} else if(arr[l] + arr[r] < x) {
l++;
} else {
r--;
}
}
return [NaN, NaN];
}
您总是可以用 O(n) 时间 O(n) space 替换 O(n lg n) 时间 O(1) space 算法，这是不正确的。这真的取决于问题，并且有许多不同的算法，它们对时间和 space 具有不同的复杂性，而不仅仅是线性或线性对数（例如 n log n）。
请注意，O(1) space 有时意味着（如您的示例）您需要修改输入数组。所以这实际上意味着你确实需要 O(n) space，但你可以以某种方式使用输入数组作为你的 space（与真正只使用常量 space 的情况相比）。更改输入数组并不总是可能或允许的。
至于在具有不同时间和space特性的不同算法之间进行选择，这取决于您的优先级。通常，时间是最重要的，所以如果你有足够的内存，你会选择最快的算法（记住这个内存只是在算法 运行 时临时使用）。如果你真的没有所需的space，那么你会选择一个更慢的算法，它需要更少的space。
因此，一般的经验法则是选择最快的算法（不仅仅是通过渐近复杂度，而是根据您的常规工作负载的实际现实世界最快执行时间）可以适应其 space要求。
要比较两种算法，首先应该明确我们比较的是什么。 如果我们的优先级是 space，则 T(n)=O(n log n) & S(n)=O(1) 的算法更好。 在一般情况下，第二个 T(n)=O(n) & S(n)=O(n) 更好，因为 space 可以补偿但时间不能。
选择算法方法时应牢记三点。
- 在最坏的情况下，应用程序 运行 顺利运行的时间。
- Space 可用性取决于程序将 运行 在的环境类型。
- 所创建函数的可重用性。
鉴于这三点，我们可以决定哪种方法适合我们的应用。
如果我有有限的 space 和合理的数据提供给它，那么条件 2 将发挥主要作用。这里，我们可以用O(nlogn)检查平滑度，并尝试优化代码并重视条件3。
（例如，Array Pair Sum 中使用的排序算法可以在我的代码的其他地方重复使用。）
如果我有足够的 space，那么按时即兴创作将是主要问题。在这里，而不是可重用性，人们将专注于编写省时的程序。
假设您的假设是正确的。 鉴于在现实生活中不存在无限资源这一事实，并且在实施解决方案时，您将尽最大努力实施最可靠的解决方案（一种不会因为您消耗了所有允许的内存而中断的解决方案），我会很明智然后一起去：
Algorithm with O(n log n) time and O(1) space complexity
即使你有大量的内存，并且你确定你永远不会耗尽你的内存，使用消耗大量内存的解决方案可能会导致很多问题（I/O read/write 速度，在发生故障时备份数据）而且我想没有人喜欢在启动时使用 2Go 内存并且随着时间的推移不断增长的应用程序，就好像存在内存泄漏一样。
我想最好是写一个测试，
实际算法，数据量（n），
和内存使用模式将很重要。
此处是 model 的简单尝试；
random() 函数调用和 mod 时间复杂度的操作，
space 复杂度的随机内存访问 (read/write)。
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <math.h>
int test_count = 10;
int* test (long time_cost, long mem_cost){
// memory allocation cost is also included
int* mem = malloc(sizeof(int) * mem_cost);
long i;
for (i = 0; i < time_cost; i++){
//random memory access, read and write operations.
*(mem + (random() % mem_cost)) = *(mem + (random() % mem_cost));
}
return mem;
}
int main(int argc, char** argv){
if (argc != 2) {
fprintf(stderr,"wrong argument count %d \nusage: complexity n", argc);
return -1;
}
long n = atol(argv[1]);
int *mem1, *mem2;
clock_t start,stop;
long long sum1 = 0;
long long sum2 = 0;
int i = 0;
for (i; i < test_count; i++){
start = clock();
mem1 = test(n * log(n), 1);
stop = clock();
free(mem1);
sum1 += (stop - start);
start = clock();
mem2 = test(n , n);
stop = clock();
free(mem2);
sum2 += (stop - start);
}
fprintf(stdout, "%lld \t", sum1);
fprintf(stdout, "%lld \n", sum2);
return 0;
}
禁用优化；
gcc -o complexity -O0 -lm complexity.c
测试；
for ((i = 1000; i < 10000000; i *= 2)); do ./complexity $i; done | awk -e '{print / }'
我得到的结果；
7.96269
7.86233
8.54565
8.93554
9.63891
10.2098
10.596
10.9249
10.8096
10.9078
8.08227
6.63285
5.63355
5.45705
在某些时候 O(n) 在我的机器上做得更好,
一段时间后，O(n*logn) 变得更好，（我没有使用交换）。