该算法使用 Big-O 表示法的时间复杂度

Question

我必须找到我创建的伪代码的时间复杂度，并使用大 O 表示法指定它。问题是当我在嵌套的 for 循环中有一个 if 语句时，我不知道如何计算它。
这是我的伪代码，括号里的是运算次数：

Algorithm largestProduct(A)
  Input array A
  Output largest product value of two elements in array A, the values and their indices
  index1 ← 0                                          (1)
  index2 ← 0                                          (1)
  n ← A length                                        (1)
  max ← 0                                             (1)
  for i ← 0 to n-1 do                                 (n)
    for j ← i + 1 to n do                             (n^2)
      if max < A[ i ] * A[ j ] then                   (?)
        max ← A[ i ] * A[ j ]
        index1 ← i
        index2 ← j
  return max, A[index1], index1, A[index2], index2

预先感谢您的帮助。

Answer 1

由于 if 语句中的操作及其条件不影响迭代次数并且它们是单个操作（常量），因此您可以将 if 语句视为 O(1).

嵌套的 for 循环确实进行了 O(n^2) 次迭代，因此，有常量的操作运行 O(n^2) 次，因此 O(n^2)*O(1)=O(n^2) 整体。

该算法使用 Big-O 表示法的时间复杂度

Time complexity of this algorithm using Big-O notation

big-o

time-complexity