在if子句中找到复杂性

Question

假设我有一个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)

Answer 1

总复杂度为O(x ³),因为您可以通过x ²操作跟随(可能)执行x ³操作.前者支配后者:O(x ³)+ O(x ²)= O(x ³).