时间戳

首页 > 解决方案 > 使用 Big-O 表示法的该算法的时间复杂度

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

问题描述


我必须找到我创建的伪代码的时间复杂度，并使用 Big-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

预先感谢您的帮助。

标签： time-complexitybig-o

解决方案

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

嵌套for循环确实会进行O(n^2)迭代，因此，有恒定数量的操作运行O(n^2)时间，使其成为O(n^2)*O(1)=O(n^2)整体。

推荐阅读