java - 算法复杂度分析混淆

Question

static int sumAfterPos(int[] A) {
  int N = A.length;
  for (int i = 0; i < N; i += 1) {
    if (A[i] > 0) {
      int S;
      S = 0;
      for (int j = i + 1; j < N; j += 1) {
        S += A[j];
      }
      return S;
    }
  }
  return 0;
}

我无法确定此代码是在 O(n^2) 还是 O(n) 中运行。我不确定return S 是否会对运行时产生很大的影响。

Answer 1

是O(N)及时。

例如，A[K] > 0 , 那么你已经有了 K脚步。然后你运行另一个 N-K步骤和返回。所以你完全有 O(N) .

假设所有A[i] < 0 ，这将使内部循环消失。所以是O(N)在这种情况下。

现在让我们说，A[0] > 0 ，这将使外循环仅重复一次，内循环将从 1 运行到 N - 1，因此总共有 1 + (N-1 - 1 + 1) = N。

现在让我们说，A[1] > 0 ，这将使外循环仅重复两次，而内循环将从 2 运行到 N - 1，因此总共有 2 + (N-1 - 2 + 1) = N。

...

现在让我们说，A[k] > 0 ，这将使外循环仅重复 k + 1 次，而内循环将从 k + 1 运行到 N - 1，因此总共有 k + 1 + (N-1 - k -1 + 1) = N。

现在让我们说，A[N-1] > 0 ，这将使外循环只重复 N 次，而内循环永远不会运行，所以总共有 N 次。