下面的方法的复杂度是多少？

发布于 2024-09-04 02:53:21 字数 249 浏览 3 评论 0原文

我仍在学习使用大 O 表示法的复杂性测量，想知道我是否正确地说以下方法的复杂性是 O(n*log4n)，其中“4”是下标。

public static void f(int n)
{
    for (int i=n; i>0; i--)
    {
        int j = n;
        while (j>0)
            j = j/4;
    }
}

原文

I'm still learning about complexity measurement using the Big O Notation, was wondering if I'm correct to say that following method's complexity is O(n*log4n), where the "4" is a subscript.

public static void f(int n)
{
    for (int i=n; i>0; i--)
    {
        int j = n;
        while (j>0)
            j = j/4;
    }
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

绮烟 2024-09-11 02:53:21

是的，你是对的，函数的复杂度是 O(n*log_4(n))

Log_4(n) = ln(n) / ln(4)并且 ln(4) 是一个常量，因此如果您的函数的复杂度为 O(n*log_4(n))，它的复杂度也为 O(n*log_4(n))代码>O(n*ln(n))

回复收藏 0 原文

泪冰清 2024-09-11 02:53:21

你的意思

public static void f(int n) 
{ 
    for (int i=n; i>0; i--) 
    { 
        int j = i;  // Not j = n.
        while (j>0) 
            j = j/4; 
    } 
}

？

在这种情况下，你也是对的。其复杂度为 O(nlogn)。使用4作为下标也是正确的，但这只会让写起来更加麻烦。

即使使用 j=n 行，其时间复杂度也是 O(nlogn)。

事实上，更准确地说，你可以说它是 Theta(n logn)。

Did you mean

public static void f(int n) 
{ 
    for (int i=n; i>0; i--) 
    { 
        int j = i;  // Not j = n.
        while (j>0) 
            j = j/4; 
    } 
}

In that case, too you are correct. It is O(nlogn). Using the 4 as subscript is correct too, but it only makes it more cumbersome to write.

Even with the j=n line, it is O(nlogn).

In fact to be more accurate you can say it is Theta(n logn).

回复收藏 0 原文