algorithm - 你如何计算函数的最坏情况时间复杂度

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(log2n)
• O(n)
• O(n^2)
• O(n+值)

Answer 1

这种情况可以看一下代码的结构和原因如下:

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

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