函数内函数的 Big-O 分析

发布于 2024-12-05 13:14:31 字数 423 浏览 0 评论 0原文

我对 Big-O 在处理函数内的函数时（分析最坏情况时）如何工作感到困惑。例如，如果您有这样的情况：

for(int a = 0; a < n; a++)
{
    *some function that runs in O(n*log(n))*
    for(int b = 0; b < n; b++)
    {
        *do something in constant time*
    }
}

整个块会在 O(n^2*log(n)) 中运行吗？因为在第一个 for 循环中，您有一个 O(n) 和一个 O(n*log( n))，所以 O(n*log(n)) 更大，因此我们取那个？或者是 O(n^3*log(n)) 因为外部 for 循环中有 O(n) 和 O(n*log(n)) ？

任何帮助表示赞赏！谢谢！

原文

I'm confused about how Big-O works when dealing with functions within functions (when analyzing worst case). For example, what if you have something like:

for(int a = 0; a < n; a++)
{
    *some function that runs in O(n*log(n))*
    for(int b = 0; b < n; b++)
    {
        *do something in constant time*
    }
}

Would this entire block run in O(n^2*log(n)), because within the first for loop, you have an O(n) and an O(n*log(n)), so O(n*log(n)) is greater, and therefore the one we take? Or is it O(n^3*log(n)) because you have an O(n) and an O(n*log(n)) within the outer for loop?

Any help is appreciated! Thanks!

分享到QQ

分享到微博

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

发布评论

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

树深时见影 2024-12-12 13:14:31

这是

O(N) * (O(N lg N) + O(N) * O(1)) = O(N) * (O(N lg N) + O(N))
                                 = O(N) * O(N lg N)
                                 = O(N^2 lg N)

因为您有 O(N lg N) 函数的 O(N) 次迭代和 O(N) 常数时间操作。 O(N lg N) + O(N) 简化为 O(N lg N) 因为 O(N lg N) > O(N)。

It's

O(N) * (O(N lg N) + O(N) * O(1)) = O(N) * (O(N lg N) + O(N))
                                 = O(N) * O(N lg N)
                                 = O(N^2 lg N)

Because you have O(N) iterations of an O(N lg N) function and O(N) constant time operations. The O(N lg N) + O(N) simplifies to O(N lg N) because O(N lg N) > O(N).

回复收藏 0 原文

人间不值得 2024-12-12 13:14:31

计算此类复杂性时，您应该添加内联或顺序函数以及乘嵌套函数。

例如，这将是 O(n)：

// O(n) + O(n) = O(2n)` which is `O(n)` (as constants are removed)
for (int i = 0; i < n; i++)
{ 
    /* something constant */ 
}
for (int j = 0; j < n; j++)
{ 
    /* something constant */ 
}

但是当函数嵌套时，会增加它们的复杂性：

// O(n) * O(n) = O(n^2)
for (int i = 0; i < n; i++)
{ 
    for (int j = 0; j < n; j++)
    { 
        /* something constant */ 
    }
}

您的示例是一个组合 - 您在另一个函数中嵌套了一些顺序操作。

// this is O(n*logn) + O(n), which is O(n*logn)
*some function that runs in O(n*log(n))*
for(int b = 0; b < n; b++)
{
    *do something in constant time*
}

// multiplying this complexity by O(n)
// O(n) * O(n*logn)
for(int a = 0; a < n; a++)
{
    // your O(n*logn)
    // your b loop
}

When calculating this type of complexity you should add inline or sequential functions and multiply nested functions.

For example, this would be O(n):

// O(n) + O(n) = O(2n)` which is `O(n)` (as constants are removed)
for (int i = 0; i < n; i++)
{ 
    /* something constant */ 
}
for (int j = 0; j < n; j++)
{ 
    /* something constant */ 
}

But when the functions are nested, multiply their complexity:

// O(n) * O(n) = O(n^2)
for (int i = 0; i < n; i++)
{ 
    for (int j = 0; j < n; j++)
    { 
        /* something constant */ 
    }
}

Your example is a combination - you've got some sequential operations nested inside another function.

// this is O(n*logn) + O(n), which is O(n*logn)
*some function that runs in O(n*log(n))*
for(int b = 0; b < n; b++)
{
    *do something in constant time*
}

// multiplying this complexity by O(n)
// O(n) * O(n*logn)
for(int a = 0; a < n; a++)
{
    // your O(n*logn)
    // your b loop
}

回复收藏 0 原文

~没有更多了~