algorithm - 以下代码 : 的总运行时间是多少

Question

以下代码的总运行时间是多少:

我得出的结论是这段代码需要 O(N log N) 次来执行，当创建类时，循环需要 O(N) 时间来执行，下面的这个 for 循环需要 log n 时间。但我对此并不完全确定，这就是我在这里问的原因。

Z z = new Z(N); 
for (int i = 0; i < N-1; i = i+2) 
  z.update(i,i+1);

Z 级:

public class Z
{ 

int[] next, prev;
Z(int N)
{
    prev = new int[N];
    next = new int[N];
    for (int i = 0; i<N; ++i)
    // put element i in a list of its own
    {
     next[i] = i;
     prev[i] = i;
        }
     }

 int first(int i)
    // return first element of list containing i
 {
     while (i != prev[i]) i = prev[i];
     return i;
 }

 int last(int i)
 // return last element of list containing i
 {
     while (i != next[i]) i = next[i];
     return i;
 }


 void update(int i, int j)
 {
     int f = first(j);
     int l = last(i);
     next[l] = f;
     prev[f] = l;
 }

 boolean query(int i, int j)
 {
 return last(i) == last(j);
 }
 }

Answer 1

总运行时间仅为O(N)。

构造函数的循环有 O(N) 个步骤。它将 next/prev 数组创建为 [0, 1, ..., N]。

z.update(i,i+1) 只需要 O(1) 时间。由于您只为每个 i=i 和 j=i+1 调用一次 update()，first(j) 和 last(i) 将分别返回 j 和 i。

在一般情况下，不可能分析 first() 和 last() 的预期复杂度，因为它们很容易包含无限循环(例如，如果当 next=[1,0] 时用 0 调用)。但是，在给出的示例中，它们将始终完全跳过 while 循环，因为对这些函数的每次调用都在尚未修改的索引上进行。