标签: asymptotic-complexity

关于大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))？

P中是否存在已证明O(n ^ 2)或更高的渐近下界的问题？(n是问题实例可以表示的位数).这不是一个功课问题,只是好奇心.

它是 f(n)=theta(h(n)) 因为 theta 是可传递的。但是任何人都可以解释为什么 h(n)=theta(f(n))。

假设我有一个if子句

if (!f(x))
{
   g(x);
}

f(x)= O(x ^ 3)的复杂度和g(x)= O(x ^ 2)的复杂度.在这种情况下,整体复杂性是多少？O(x ^ 5)？还是O(x ^ 3)？

我想增加问题的大小.

while(z(x))
{
  for(p(x))
  {
     if (!f(x))
     {
       g(x);
     }
  }
}

其中,z(x)= O(x ^ 5),p(x)= O(x),f(x)= O(x ^ 3),g(x)= O(x ^ 2)

我试图了解DFS 的复杂性如何/为什么是 O(V+E)。这是我分析伪代码迭代 DFS 复杂性的尝试。

DFS(G, t)
{

1   stack S = new empty Stack of size G.|V|  ... O(1)
2   S.push(t)                                ... O(1)

3   while(S is not Empty)                    ... O(|V|), this will always be =<|V|
    {
4       u = S.pop()                          ... O(1)

5       if(u.visited = false)                ... O(1)
        {
6            u.visited = true                ... O(1)

7            for-each edge (u,v) in G.E      ... O(|E|), this will always be =<|E|
8                if(v.visited = false)       ... O(1)
9                    S.push(v) …

我在编程实践网站上找到了这个解决方案,它说复杂性是O(N).但是,它看起来更像是O(N ^ 2).有人可以告诉我为什么这是O(N)？

public static void transposeMatrix(int[][] matrix) {
    int n = matrix.length - 1;
    int temp = 0;
    for(int i = 0; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}

鉴于再次发生:
A(n) = A(n-1) + n*log(n).
我如何找到时间复杂度A(n)？

我对IP和FP的性能有疑问.假设我有一个计算第n个Fibonacci数的函数.

在命令式编程中,我可以选择使用迭代方式,递归或动态编程来计算第n个Fibonacci数.当然,与递归渐近相比,迭代方式和动态编程将表现得更好.

在函数式编程中,假设没有涉及的状态,那么我只能以递归的方式进行.

在这种情况下,这并不意味着功能编程在效率方面与渐进式编程相比总是表现得相同或更慢(渐近)？

现实世界的函数式编程如何处理这个问题？

假设当n变为无穷大时f(n)变为无穷大.

这是一个家庭作业问题,我希望得到一个想法/指导,而不是完整的答案.

我们已经知道一些算法的渐近时间复杂度是n的函数,如

O(log*n),O(log n),O(log log n),O(n ^ c),0 <c <1,....

我可以知道作为n的函数的最小算法的渐近时间复杂度是多少？

• 更新1:我们用n来寻找渐近时间复杂度函数.O(1)是最小的,但它没有n.

• 更新2:O(1)是我们可以进行的最小时间复杂度,但是n的下一个最小的众所周知的函数是什么？据我研究:

  O(alpha(n)):逆Ackermann:使用不相交集的每次操作的摊销时间

  或O(log*n)迭代对数Hopcroft和Ullman在不相交集上的查找算法

我的算法类的作业声称O(n ³)比O(2 ⁿ)更有效.

当我将这些函数放入图形计算器时,对于非常大的n(从n = 982左右开始),f(x)= 2 ^x似乎始终更有效.

考虑到对于函数f(n)= O(g(n)),对于大于某个n _0的所有n,它必须更小,这不意味着从n = 982我们可以说O(2 ⁿ)效率更高？