1

我必须逐行计算算法的时间复杂度或理论运行时间（给定伪代码）作为 T(n)。我已经尝试过了，但有几件事让我感到困惑。例如，“if”语句的时间复杂度是多少？以及如何处理嵌套循环？下面的代码以及我的尝试进行了评论。

长度[A] = n

    for i = 0 to length[A] - 1    // n - 1 
      k = i + 1                   // n - 2
      for j = 1 + 2 to length[A]  // (n - 1)(n - 3)
        if A[k] > A[j]            // 1(n - 1)(n - 3)
          k = j                   // 1(n - 1)(n - 3)
      if k != i + 1               // 1(n - 1)
        temp = A[i + 1]           // 1(n - 1)
        A[i + 1] = A[k]           // 1(n - 1)
        A[k] = temp               // 1(n - 1)
4

1 回答 1

1

Blender 是对的，结果是 O(n^2)：两个嵌套循环，每个循环的迭代次数取决于n.

更长的解释：

在这种情况下，if 并不重要：由于 O 表示法仅查看算法的最坏情况执行时间，因此您只需选择对整体执行时间更差的执行路径。由于在您的示例中，两个执行路径（k != i+ 1是 true 或 false）对运行时没有进一步的影响，因此您可以忽略它。如果有第三个嵌套循环，也运行到n，在 内if，你最终会得到 O(n^3)。

逐行概述：

for i = 0 to length[A] - 1    // n + 1 [1]
  k = i + 1                   // n
  for j = 1 + 2 to length[A]  // (n)(n - 3 + 1) [1]
    if A[k] > A[j]            // (n)(n - 3)
      k = j                   // (n)(n - 3)*x [2]
  if k != i + 1               // n
    temp = A[i + 1]           // n*y [2]
    A[i + 1] = A[k]           // n*y
    A[k] = temp               // n*y

[1]for循环语句将被执行 n+1 次，其值为i：0(true, continue loop), 1(true, continue loop), ..., length[A] - 1(true, continue loop), length[A](false, break loop)

[2] 在不知道数据的情况下，您必须猜测if' 条件为真的频率。这个猜测可以通过引入一个变量 0 <= x<= 1 在数学上完成。这与我之前所说的一致：x独立于n并因此仅作为一个常数因素影响整体运行时复杂性：你需要看看执行路径。

于 2013-01-23T12:12:17.460 回答