你如何解决函数的最坏情况时间复杂度

Question

所以如果我们有这样的问题我们如何解决这个问题:

下面方法的最坏情况时间复杂度是多少(其中n是array.length):

boolean search(int[] array, int value) {
  for (int j = 0; j < array.length; i++)
    if (array[j] == value)
      return true;
  return false;
}

• O(1)
• O(log2 n)
• 上)
• 为O(n ^ 2)
• 为O(n +值)

Answer 1

在这种情况下,您可以查看代码的结构和原因,如下所示:

我可以看到,for (int j = 0; j < array.length; j++)意味着j取值为从0到array.length - 1.这意味着这是一个关于数组长度的线性循环.循环内部和下方的操作在恒定时间内发生.

所以现在的问题是:最坏的情况是什么？最糟糕的情况是根本没有在数组中找到该元素,这意味着您将遍历整个数组.因此,算法是O(n)最坏的情况.