带for循环的if else选择语句的Big O表示法

Question

if (A[1][1] == 0)
  for(i=0; i<n; i++)
    for (j=0; j<n; j++)
      A[i][j] = 0;
else
  for (i=0; i<n; i++)
    A[i][i] = 1;

我正在寻找此代码的大O表示法。我试图了解该程序，但无法掌握它。

Answer 1

完成以下步骤所需的时间与n成比例，因此以下为O（n）：

for (i=0; i<n; i++)
  A[i][i] = 1;

完成以下操作所需的时间与n*n成正比，即n ²，因此以下内容为O（n ²）：

for(i=0; i<n; i++)
  for (j=0; j<n; j++)
    A[i][j] = 0;

该代码段将执行其中之一，但不能同时执行。因此，最坏的情况受这两个选项中较差的约束，所以它是O（n ²）。