时间戳

首页 > 解决方案 > 多项式函数的复杂度是什么意思？

algorithm - 多项式函数的复杂度是什么意思？

问题描述

我正在新研究算法复杂性、大o、欧米茄符号等。

例如，我可以理解嵌套 for 循环之类的示例。我根据 n 计算内部语句将执行多少次，这给出了复杂性。例如

int a = 1;
for(i=0; i<n; i++){

    for(j=0; j<n; j++){
    a = a*2;
    }
}

我可以理解，上面这个的 big-o 是 O(n^2)。但是，我也遇到过这样的问题，

O( ) 函数复杂度 (n^3 + 7) / (n + 1)

乍一看，作为一种直觉，我想认为当 n 趋于无穷大时，n^3是分子中的主导项，n是分母中的主导项。因此，复杂度为 O(n^3/n) = O(n^2)。但是，尽管看起来合乎逻辑，但它也不合逻辑。简而言之，我不确定这种微积分的方法是否正确。

但更重要的是，我也不明白复杂性在函数的情况下意味着什么。看起来对于任何 n 值，只会执行有限数量的操作：取数字 n 的立方体，加 7，除以 (n+1)。所以我不明白复杂性是如何受到 n 的影响的。

标签： algorithmtime-complexitybig-o

解决方案

这是一个很好的问题，因为您已经发现练习的措辞有歧义。“函数的 O() 复杂度”没有得到很好的定义。您需要区分以下内容：

  1. 以 O(...) 表示的算法实现的（例如时间）复杂度。示例：带链表的快速排序。
  2. 以 O(...) 表示的算法的（例如时间）复杂度。示例：快速排序。
  3. 以 O(...) 表示的决策问题的（例如时间）复杂度。示例：给定列表是否已排序？
  4. 以 O(...) 表示的函数问题的（例如时间）复杂度。示例：对给定列表进行排序。
  5. 以 O(...) 表示的数学函数的渐近上界。示例： 的上限(n^3 + 7) / (n + 1)。

我的猜测是 5. 是预期的意思，但措辞具有误导性，甚至可以说是错误的。它也可能是＃4，但这意味着：找到可用于计算给定多项式的任何可能算法的时间复杂度的上限，这是一个关于多项式的相当不寻常的问题。

推荐阅读