问题标签 [big-o]

什么是最坏情况时间复杂度 t(n) ：- 我正在阅读这本关于算法的书，并举例说明如何为 .... 获取 T(n)，例如选择排序算法

就像我正在处理 selectionSort(A[0..n-1])

让我写一个伪代码

--------我也会用C#写的----------------

===================

现在如何获得 t(n) 或众所周知的最坏情况时间复杂度

我了解 Big-O 表示法，但我不知道如何为许多函数计算它。特别是，我一直试图弄清楚斐波那契数列的原始版本的计算复杂性：

斐波那契数列的计算复杂度是多少，它是如何计算的？

以下嵌套循环的 Big-O 时间复杂度是多少：

还会是O(N^2)吗？

参考这个答案，什么是 Theta（紧界）？

Omega 是下限，很容易理解，是算法可能花费的最短时间。我们知道 Big-O 是上限，表示算法可能花费的最长时间。但我对Theta一无所知。

我有一个 5000 个整数的排序数组。我能以多快的速度判断一个随机整数是否是数组的成员？一般来说，C 和 Ruby 的答案会很好。

数组值的形式为

其中c可以是 1 到 5000 之间的任何整数。

例如：

有时我看到 Θ(n) 带有奇怪的 Θ 符号，中间有东西，有时只是 O(n)。只是懒惰打字，因为没有人知道如何输入这个符号，还是意味着不同的东西？

我更喜欢尽可能少的正式定义和简单的数学。

我需要计算以下代码的时间复杂度：

是O(n^2)吗？

有时我在试图用 O(x) 表示法估计算法的速度时完全被愚弄了，我的意思是，我真的可以指出顺序是 O(n) 还是 O(mxn)，但对于那些是 O(lg( n)) 或 O(C(power n)) 我认为我在那里遗漏了一些东西......那么，对于快速忽略算法的简单估计，你有什么技巧和窍门？

作为我正在寻找的一个例子，这里有一些简单的（可能是错误的，但尽我所能）：

• O(n)：如果有一个从 1 到 n 的简单循环（或其中几个，但没有嵌套。
• O(mxn)：另一个嵌套循环，其中限制为 m 和 n。

提前致谢。

我可能很快就会教授“Java 速成课程”。虽然假设观众成员会知道 Big-O 表示法可能是安全的，但假设他们会知道各种集合实现上的各种操作的顺序可能是不安全的。

我可以花时间自己生成一个汇总矩阵，但如果它已经存在于公共领域的某个地方，我肯定想重用它（当然，有适当的信用。）

有人有任何指示吗？