没有实际测试（这是一种冒险行为！），我想说O(n log n)时间复杂度且O(1)空间复杂度的算法可能比O(n)时间复杂度且O(n)空间复杂度的算法更快，但仍然可能不是最优算法。
首先，让我们从高层次的角度来看待这个问题，忽略你所描述的算法的具体细节。需要记住的一个细节是，虽然O(n)时间复杂度的算法渐近上比O(n log n)时间复杂度的算法更快，但它们只快了对数因子。需要注意的是，考虑到宇宙中的原子数量约为1080（感谢物理学！），宇宙中原子数量的以2为底的对数约为240。从实用的角度来看，这意味着您可以将额外的O(log n)因子视为常数。因此，要确定O(n log n)算法在特定输入上是否比O(n)算法更快或更慢，您需要了解大O符号隐藏的常数有哪些。例如，运行时间为600n的算法将比运行时间为2n log n的算法慢，不管n的大小如何，只要它适合于宇宙中的任何n。因此，从外部表现的角度来看，为了评估哪个算法更快，您可能需要对算法进行一些剖析，以确定哪个算法更快。
然后还有缓存和引用局部性的影响。计算机内存中有大量缓存，这些缓存针对读写相邻的情况进行了优化。缓存未命中的成本可能非常巨大，比命中慢上数百或数千倍，因此您希望尽量将其减少。如果算法使用O(n)内存，则随着n变得越来越大，您需要开始担心内存访问的密集程度。如果它们分散在不同位置，那么缓存未命中的成本可能会迅速累积，从而显著增加时间复杂度隐藏在大O符号中的系数。如果它们更顺序地排列，那么您可能不需要太担心这个问题。
您还需要注意可用的总内存。如果您的系统有8GB的RAM，并且有一个包含十亿个32位整数的数组，则即使有合理的常数，如果需要O(n)的辅助空间，则无法将辅助内存放入主内存中，并且它将开始被操作系统换出页面，从而大大降低运行时间。
最后还有随机性的问题。基于哈希的算法具有预期的快速运行时间，但如果您使用了糟糕的哈希函数，则算法可能会变慢。生成好的随机位很难，因此大多数哈希表只采用“相当不错”的哈希函数，冒着使算法性能退化的最坏情况输入的风险。
那么这些问题在实践中是如何发挥作用的呢？让我们来看看算法。O(n)-时间，O(n)-空间算法通过建立一个哈希表来存储数组中的所有元素，以便您可以轻松地检查给定的元素是否存在于数组中，然后扫描数组，查看是否有一对元素的和为总和。考虑以上因素，让我们思考一下这个算法的工作原理。从经验来看：
请注意，通常情况下，如果问题适合于比瓶颈存储器更快的内存，则随机访问速度“快”。（例如，如果磁盘是瓶颈，则主内存足够快以进行随机访问 - 如果主内存是瓶颈，则CPU缓存足够快以进行随机访问）
比较两个算法，首先需要明确我们要比较的是什么。 如果我们的优先考虑空间，那么具有 T(n)=O(n log n) & S(n)=O(1) 的算法更好。 在一般情况下，第二个具有 T(n)=O(n) & S(n)=O(n) 的算法更好，因为空间可以弥补但时间无法。
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];
}
在选择算法方法时，应该牢记三点。
考虑到这三点，我们可以决定哪种方法适合我们的应用程序。
如果我有限的空间和合理的数据供应，那么条件2将起主要作用。在这里，我们可以检查 O(nlogn) 的平稳性，并尝试优化代码并重视条件3。（例如，在数组对求和中使用的排序算法可以在我的代码的其他地方重复使用。）
如果我有足够的空间，则改进时间将是主要关注点。在这里，与可重用性不同，人们会专注于编写高效的程序。
时间复杂度为O(n log n)，空间复杂度为O(1)的算法即使你有大量的内存，并且你确信你永远不会耗尽你的内存，使用消耗大量内存的解决方案也可能导致许多问题（I/O读/写速度，备份数据在出现故障的情况下）。我想没有人喜欢在启动时使用2Go内存并随着时间的推移不断增长，就像存在内存泄漏一样。#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 $1 / $2}'
我得到的结果：
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) 表现更好（我没有使用交换）。