Ak2*_*399 66 algorithm implementation time-complexity
假设我们有一个问题，某个算法（我们称之为算法_1）的时间复杂度为 ，O(n^2)另一个算法（我们称之为算法_2）的时间复杂度为O(n)，但实际上我们看到n < 1000算法_1 更快，否则算法_2 更快是比较快的。
为什么我们不能直接写这样的代码：
if ( n < 1000)
do algorithm_1
else
do algorithm_2
这是程序员真正做的事情还是有缺点？
对于较小的程序，这似乎是一个好主意。
Car*_*orc 74
这确实发生在现实世界中！例如，一个著名的排序算法是Timsort：
以下实施细节：
我们将运行的大小视为 32，并将输入数组划分为子数组。
我们对大小等于运行简单插入排序的片段进行逐一排序。对各个部分进行排序后，我们使用合并排序将它们一一合并。
每次迭代后，我们将合并子数组的大小加倍。
插入排序的复杂度为 O(N^2)，但对于小型列表来说速度更快，合并排序的复杂度为 O(N logN)，因此对于较长的列表更好。
另一个例子是 introsort，C++ 标准库中使用的排序：
Introsort 或内省排序是一种混合排序算法，可提供快速平均性能和（渐近）最佳最坏情况性能。它从快速排序开始，当递归深度超过基于要排序的元素数量（的对数）的级别时，它切换到堆排序，当元素数量低于某个阈值时，它切换到插入排序。它结合了三种算法的优点，实际性能与典型数据集上的快速排序相当，并且由于堆排序而在最坏情况下运行时间为 O(n log n)。由于它使用的三种算法都是比较排序，所以它也是比较排序。
对单个任务使用更多算法的缺点显然是增加了复杂性。如果您正在为将被重复使用数百万甚至数十亿次的编程语言编写标准库代码，那么这是值得的。对于专注于通过仅实现一种算法来节省开发人员时间而不是机器时间的小型项目来说，通常是更好的选择。
参考：
Spe*_*tre 34
是的，这很常见。例如，bignums 乘法可以通过多种方式完成：
\nO(N^2)O((N^1.585)O(N*log(N)*(log(log(N))))因此，根据使用的输入变量，使用位宽最快的版本（我一直使用它来对 bignum 进行性能关键的“低级”数学运算，因为它们被用作更高操作的构建块，如果没有它，它就会不能在“整个/实际”数字范围上以最佳速度工作）。
\n但是，阈值取决于计算硬件架构、使用的编译器，有时甚至是代码使用情况，因此它们可能会因每台计算机而异，因此为了确保最佳性能，有时会在程序启动或配置阶段测量阈值，而不是使用硬编码值。
\n这通常用于具有多种输入大小的函数，也不适用于简单的函数，因为if在算法之间进行选择的初始语句也会影响性能（分支）。在一些“罕见”的情况下，我认为你可以无分支地做到这一点。例如，如果输入大小也是模板的输入参数，甚至可能是宏的输入参数，例如，如下所示（C++）：
double matrix<1>::det() { return a[0][0]; }\ndouble matrix<2>::det() { return (a[0][0]*a[1][1])-(a[0][1]*a[1][0]); }\ntemplate <DWORD N> double matrix<N>::det()\n {\n double d=0.0; int j;\n matrix<N-1> m;\n for (j=0;j<N;j++)\n {\n m=submatrix(0,j);\n if (int(j&1)==0) d+=a[0][j]*m.det();\n else d-=a[0][j]*m.det();\n }\n return d;\n }\n正如您所看到的，根据输入大小，行列式有三种不同的方法，但没有选择分支。但是，只能使用硬编码阈值。
\n您还可以使用函数指针来实现此目的，例如（C++）：
\nint algoritm1(int x){ return 10; }\nint algoritm2(int x){ return 20; }\nint algoritm3(int x){ return 30; }\nint (*functions[4])(int x)={ algoritm1,algoritm2,algoritm3,algoritm3 };\nint function(int x)\n {\n return functions[(x>>10)&3](x);\n }\n因此，对于x最多 1024 个使用 algoritm1 的情况，最多 2048 个使用算法 2 的情况，对于其余的情况，使用算法 3 也没有任何分支。在这里，您可以拥有动态阈值（不是那么灵活，但仍然可用），因此您可以按 2 的某个幂对 x 范围进行采样（就像我所做的 2^10=1024 一样），并且只使用重复项。因此，例如，如果舍入阈值是3*1024和5*1024，您可以这样做：
int algoritm1(int x){ return 10; }\nint algoritm2(int x){ return 20; }\nint algoritm3(int x){ return 30; }\nint (*functions[8])(int x)=\n {\n algoritm1,\n algoritm1,\n algoritm1,\n algoritm2,\n algoritm2,\n algoritm3,\n algoritm3,\n algoritm3\n };\nint function(int x)\n {\n return functions[(x>>10)&7](x);\n }\n因此，您也可以使用这种方法根据运行时测量的阈值创建函数指针数组......
\nDad*_*ada 19
正如另一个答案所说：是的！
另一个例子是Java的HashMap类。此类使用单独的链接解决冲突。最初，每个桶都包含一个链表，但如果该链表的长度增长超过某个阈值（Java 8 中为 8），它就会转换为 TreeNode（TreeNode 被实现为红黑树）。通过链表查找桶中的项目的时间复杂度为 O(n)，而 TreeNode 的时间复杂度为 O(log n)。
有趣的是，使用链表代替TreeNode并不是（主要）是为了节省时间，而是为了节省空间。源代码中的一条注释说：
由于 TreeNode 的大小约为常规节点的两倍，因此仅当 bin 包含足够的节点以保证使用时我们才使用它们
mou*_*ail 17
其他答案提到了许多高级算法，它们结合了许多原始算法来创建更高效的高级算法，包括：
\n请注意，复杂度越高，运行时间越差，这里使用的算法是递归的。这意味着他们将在较小的数据位上调用自己。这意味着，即使数据结构的大小足以使复杂性更好的算法更快，它最终也会减少到一个或多个小规模的问题，即使一n开始很大。
这意味着，即使对于n最初使用递归算法的大型问题，一旦问题规模减小到足以使其可行，就可以通过切换到更快的算法来获得巨大的性能优势。
这里的其他答案给出了很多例子，但我想对它们进行扩展，其中一个主要原因是有时使用高时间复杂度算法。
当谈论算法的空间/时间复杂度时，通常意味着我们指的是算法的最坏情况，或者可能是平均情况。然而，现实世界的数据集和问题通常具有可利用的模式，它们可能更接近算法的最佳情况而不是最坏情况。
考虑几个具体的例子：
Timsort是一种混合排序，主要使用归并排序，其性能相对较高，时间复杂度为O(n log n)，但它也故意使用了几种性能较差的算法。它以这种方式设计的原因是，它的作用就像一个状态机，观察正在排序的任何数据是否已经有点排序，如果是的话，就会选择一个在存在这种顺序的情况下表现良好的适当算法。（另请参阅自适应排序。）
压缩算法通常在最坏的情况下会产生更大的压缩大小，但人们实际想要压缩的数据不是随机的；视频、音频、文本都有可以利用的模式，这意味着压缩可以节省大量空间。
在形式验证中，我们一直在解决 NP 完全问题、指数问题和不可判定问题（所有这些问题都使用比 O(n\xc2\xb2) 差得多的算法（假设可能永无休止的搜索可以被视为一种算法））。
\n以太坊 智能合约语言Solidity 的编译器与SMT求解器Z3接口，以尝试正式证明asserts代码中的 总是成立，并且该问题是不可判定的。
还有很多例子。它与输入的大小无关，而更多地与运气和输入的结构有关，在该结构中，算法不会达到最坏情况的复杂性（例如，冒泡排序）在最坏的情况下是 O(n\xc2\xb2) ，但如果数组几乎按某种方式排序，则可以在线性时间内运行）。
\n小智 5
在大多数NP 类型问题中，您必须使用时间复杂度很高的近似算法或强力/低效算法。
\n有许多取决于输入的分而治之算法，并且复杂性可能会根据给出的输入类型而变化，例如排序、搜索、算术等。
\n大多数算法都会接受输入，并且输入确实有所不同，因此基本上正在使用的每个现实世界算法都是由较小的算法组成，这些算法在特定类型的输入上表现良好。并且将对那些特定算法进行研究和发展，以提高这些算法的复杂性，但您也必须意识到时间复杂度并不总是衡量算法速度的好方法，因为它\xe2\x80\x99s只是在趋向无穷大时对它的增长设置一个限制和一个关系（不计算较小的常数或那些 O(1) 指令的制作方式）。
\n快速排序的较旧实现使用插入排序，因为它对于小数据集有效，这比大多数其他简单的二次算法（例如选择排序或冒泡排序）要好。
\n还有另一种用例很难通过设计选择来计算，例如加密货币挖掘算法和CPU 周期测量......
\n