algorithm - 一个涵盖所有时间复杂性的问题

Question

这里有大学老师。我试图找到一个有意义的（实用的）代码示例，以 ELi5 的方式为初学者说明不同的时间复杂度。代码应该以恒定的复杂性开始，然后通过添加一小段代码逐渐增加复杂性：.., logn, n, nlogn, n^2, 2^n, ..

我想我可以通过一个具有较小增量更改的示例来更好地解释它，而不是将上下文从搜索切换到排序到蛮力算法。

标签： algorithmperformancetimebig-ocomplexity-theory

Answer 1

任何例子都是人为的。但这是一个做得相当好的。

让vec是一个排序的数字数组、i一个整数和x另一个数字。依次回答下列问题。

1. O(1)的价值是vec[i]多少？
2. O(n)是否在线性搜索x范围内？vec
3. O(log(n))是否在二进制搜索x范围内？vec
4. O(n^2)x范围内的两个元素的和vec是双循环吗？
5. O(n log(n))是x两个元素的总和，vec第一个是线性搜索，第二个是二分搜索。（简化技巧，对第二个较小的二进制文件进行线性搜索。然后重用您的代码 3。）
6. O(2^n)是递归x的任何元素子集的总和吗？vec
7. （伪多项式）记忆前面的解。讨论内存与速度的权衡。