算法的复杂性 [英] Complexity of an algorithm

问题描述

我学习了一个测试，发现了这个问题，所以我做了以下，是正确的吗？

while循环运行在O（log3n）。

在for循环运行在约O（（N-（一些数学））* log2n），因为我有减号是线性的，我说，整个方法运行在O（nlogn），除非我错了，它的东西，像

O（（N-（N / log3n））* log2n）＆LT; - 不完全是，但相当，不能真正弄明白

。

是负线性这里还是不是？如果没有什么是正确的比戈？

 公共无效美孚（INT N，INT M）
{
    INT I =米;
    而（ⅰ→100）
     I = I / 3;
    对于（INT K = 1; K＆GT; = 0; K--）
    {
        为（诠释J = 1; J＆n种;Ĵ* = 2）
         System.out.print（K +\ t的+ J）;
        的System.out.println（）;
    }
}
 

解决方案

在 while循环运行O（logm）。

在while循环已经结束，我为＆lt; = 100，所以下一个for循环将运行在100倍

内环将运行 O（LOGN）倍，为外循环的每个迭代。所以，总时间为 O（logm + 100 * LOGN） = O（logm + LOGN）。

I'm studying for a test and saw this question , so I did the following, is it correct?

the while loop runs at O(log3n).

the for loop runs at about O((n-(some math))*log2n) so because I have the minus symbol which is linear, I say that the whole method runs at O(nlogn), unless I'm wrong and it's something like

O((n-(n/log3n))*log2n) <- not exactly but quite, can't really figure it out.

is the minus linear here or not? if not what is the correct bigO?

public void foo (int n, int m)
{
    int i = m;
    while (i>100)
     i = i/3;
    for (int k=i; k>=0; k--)
    {
        for (int j=1; j<n; j*=2)
         System.out.print(k + "\t" + j);
        System.out.println();
    }
}

解决方案

The while loop runs in O(logm).

After the while loop has finished, i is <= 100, so the next for loop will run at most 100 times.

The inner loop will run O(logn) times, for each iteration of the outer loop. So total time is O(logm + 100*logn) = O(logm + logn).

这篇关于算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！