什么是伪多项式时间？它与多项式时间有何不同？
伪多项式时间是什么？它与多项式时间有何不同？一些运行在伪多项式时间的算法，其运行时间类似于O(nW)（对于0/1背包问题）或O(√n)（对于试除法）；为什么这不算作多项式时间？
JavaScript数组的大O表示法
JavaScript中的数组很容易通过添加和删除项进行修改。这在某种程度上掩盖了大多数语言中数组是固定大小，并需要复杂操作来调整大小的事实。似乎JavaScript使编写性能较差的数组代码变得容易。这引出了一个问题： 关于数组性能，我可以从JavaScript实现中期望什么样的性能（大O时间复...
理解Dijkstra算法的时间复杂度计算
根据我的理解，使用下面给出的邻接列表计算Dijkstra算法的时间复杂度为大O符号。但是它并没有像预期的那样得出结果，所以我逐步理解了它。 每个顶点可以连接到(V-1)个顶点，因此每个顶点的相邻边数为V-1。假设E表示与每个顶点相连的V-1条边。 在最小堆中查找和更新每个相邻顶点的权重是O...
什么会导致算法具有O(log log n)的复杂度？
这个早期的问题讨论了一些可能导致算法具有 O(log n) 复杂度的因素。 什么会导致算法具有时间复杂度 O(log log n)？
下界和紧密界的区别是什么？
参考这个答案，什么是Theta（紧密界）？ Omega是下界，也就是算法可能花费的最短时间，我们都比较理解。而我们知道Big-O是上界，表示算法可能花费的最长时间。但是我对Theta一无所知。 Theta（紧密界）描述了算法的确切复杂度，即算法运行时间的上限和下限相同。与Big-O类似，T...
欧几里得算法的时间复杂度
我很难确定欧几里得算法的时间复杂度。这个伪代码如下： function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a 看起来这取决于a和b。我认为时间复杂度为O...
这个算法对于“Hello World”而言是否技术上是O(1)的？
对于 "Hello, World!" 这个问题，这是否可以被归类为一个 O(1) 的算法？public class Hello1 { public static void Main() { DateTime TwentyYearsLater = new DateTime...
Big O(logn) 是以自然对数为底的对数吗？
对于二叉搜索树类型的数据结构，我看到它的大O表示通常写作O(logn)。这里小写的“l”表示对数使用自然对数的底数e吗？抱歉问题比较简单，但我一直很难区分不同的隐含对数。 针对二叉搜索树这种数据结构，其时间复杂度通常用O(logn)来表示。这里的小写字母"l"代表以自然对数为底数e的对数，即...
什么因素会导致算法具有O(log n)的复杂度？
我对大 O 记号的了解有限，当等式中出现对数项时，我更加困惑。 有人能否用简单的语言解释一下 O(log n) 算法是什么？对数从哪里来？ 这特别是在我试图解决这个期中练习题时出现： 让 X(1..n) 和 Y(1..n) 分别包含两个整数列表，每个列表都按非降序排序。给出一种 O...
O(n!)的例子是什么？
什么是一个 O(n!) 函数的代码示例？它应该在参考 n 的情况下以适当数量的操作运行；也就是说，我正在询问时间复杂度。