这里是一位大学讲师。我试图找到一个有意义(实用)的代码示例,以 ELi5 方式为初学者说明不同的时间复杂度。代码应该以恒定的复杂性开始,然后通过添加一小段代码来逐渐增加复杂性:.., logn, n, nlogn, n^2, 2^n, ..
我想我可以用一个有小的增量变化的例子来更好地解释它,而不是将上下文从搜索切换到排序再到暴力算法。
最佳答案
任何例子都是虚构的。但这里有一个做得相当好的。
令 vec
为已排序的数字数组,i
为整数,x
为另一个数字。为了回答以下问题。
O(1)
vec[i]
的值是多少?O(n)
通过线性搜索,x
是否在vec
的范围内?O(log(n))
通过二分查找,x
是否在vec
的范围内?O(n^2)
x
是双循环中vec
范围内的两个元素之和吗?<O(n log(n))
是x
通过对第一个二元线性搜索得到的vec
的两个元素之和搜索第二个。 (简化技巧,对第二个较小的二进制文件进行线性搜索。然后重用 3 中的代码。)O(2^n)
x
是vec
的任意元素子集通过递归得到的总和吗?- (伪多项式)记住先前的解决方案。讨论内存与速度的权衡。
关于algorithm - 一个问题涵盖所有时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60768424/