问题标签 [asymptotic-complexity]

给出以下函数的最小 O() 估计值：

如果你们可以，请解释答案而不是给我。像这样的问题将在我的中期进行，我想了解这一点。

谢谢

堆栈中的每次插入都是 O(1) ，那么插入“n”个元素所需的时间是 O(n) 吗？我们也可以对哈希表说同样的话吗？在平均情况下，在哈希表中插入“n”个元素所需的时间 = O(n) ？

我有一个关于渐近符号的测试，有一个问题：

考虑以下：

O(o(f(n)) = o(f(n))

1. 使用渐近符号的约定，用文字写出陈述的含义。
2. 陈述是真的还是假的？证明合法。

我弄错了（不完全记得我写了什么），但我认为是这样的：

对于任何函数 g(n) = o(f(n))，都有一个函数 h(n) = o(f(n))，因此 h(n) = O(f(n))。

这是对的吗？

对于（2），我不完全确定。有人可以帮我解决这个问题吗？

提前致谢。

我问的是关于 Top K 算法的问题。我认为 O(n + k log n) 应该更快，因为好吧..例如，如果您尝试插入 k = 300 和 n = 100000000，我们可以看到 O(n + k log n)更小。

但是，当我使用 C++ 进行基准测试时，它显示 O (n log k) 的速度要快 2 倍以上。这是完整的基准测试程序：

find_topk 的方法是在 O(n) 中构建一个大小为 n 的完整堆，然后将堆的顶部元素移除 k 次 O(log n)。find_topk2 的做法是构建一个大小为 k (O(k)) 的堆，使得 max 元素在顶部，然后从 k 到 n，比较看是否有任何元素小于顶部元素，如果是则 pop顶部元素，并推送新元素，这意味着 n 次 O(log k)。两种方法的编写方式都非常相似，因此我不相信任何实现细节（如创建临时对象等）会导致除了算法和数据集（随机）之外的差异。

我实际上可以分析基准测试的结果，并且可以看到 find_topk 实际上调用比较运算符的次数比 find_topk2 多得多。但我对理论复杂性的推理更感兴趣......所以两个问题。

1. 忽略实现或基准，我期望 O(n + k log n) 应该比 O(n log k) 更好是错误的吗？如果我错了，请解释为什么以及如何推理以使我可以看到 O(n log k) 实际上更好。
2. 如果我期望没有 1 没有错。那么为什么我的基准测试显示不是这样呢？

我认为这可能是关于大 O 表示法的初学者问题。例如，假设我有一个算法，它递归地分解整个列表（O（n）），然后将它重新组合在一起（O（n））。我假设这意味着效率是 O(n) + O(n)。这是否简化为 2O(n)、O(2n) 或 O(n)？根据我对这个符号的了解，它将是 O(2n) 并且使用渐近符号规则，您可以删除 2，从而得到 O(n) 的效率。

但是，如果我们试图找到一个下限，这条规则是否仍然适用？如果 Ω(n) + Ω(n) = Ω(2n)，你还能去掉 2 吗？我认为不会，因为您实际上会降低下限（因为 n < 2n）。

在 CLRS（Cormen、Leiserson、Rivest 和 Stein的算法简介）中，对于一个函数

f ( n ) =一个² + bn + c

他们说

假设我们采用常数c ₁ = a /4、c ₂ = 7 a /4 和n ₀ = 2·max(| b |/ a , √(| c |/ a ))。
那么 0 ≤ c ₁ n ² ≤ an ² + bn + c ≤ c ₂ n ²对于所有n ≥ n ₀。
因此f ( n ) 是 Θ( n ² )。

但是他们没有具体说明这些常量的值是如何来的？
我试图证明它，但不能。
请告诉我这些常数是怎么来的？

作为 n 的函数，以下代码片段的运行时间是多少？

“确切答案”是指在确定渐近运行时间之前与代码相关的方程式。

关于大 O 符号有很多问题，但我没有找到这个问题的明确答案。

我们这样写：
O(5n) = O(n)
和
O(3n^2 + n + 2) = O(n^2)

我们可以这样写：
O(2^(2n)) = O(2^n)？

对数复杂度也一样：O(n log(4n)) = O(n log(n))？

我想渐近地比较以下函数，然后按升序排列它们。还要求正确解释 lg((√n)!), lg(SquareRoot(n!)), SquareRootlg(n!), (lg(√n))!, (SquareRoot(lg n))!, SquareRoot( lg n)!

有谁知道如何执行这样的计算示例：

O(n^2) + THETA(n) + OMEGA(n^3) = ?

或者

O(n^2) * THETA(n) * OMEGA(n^3) = ?

一般来说，如何添加和乘以不同的渐近符号？