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

Question

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

我想我可以用一个有小的增量变化的例子来更好地解释它，而不是将上下文从搜索切换到排序再到暴力算法。

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. (伪多项式)记住先前的解决方案。讨论内存与速度的权衡。