如何记录一个算法在 \mathcal O（n）中完成

Question

我有一个算法，我想标记它执行所需的时间。最小工作示例是

\documentclass[a4paper]{scrartcl} 
\usepackage[ruled,vlined]{algorithm2e}
\begin{document}
\begin{algorithm}[H]
\BlankLine
$N \leftarrow a_1$\;
$K \leftarrow a_1$\;
\BlankLine
\For{$i \leftarrow 2$ \KwTo $n$}{
    $N \leftarrow \max (N , a[i]) $\;
    $K \leftarrow \min (K, a[i])$\;
}
\end{algorithm}
\end{document}

我想要实现的目标：

\For{$i \leftarrow 2$ \KwTo $n$}{
    $N \leftarrow \max (N , a[i]) $\;
    $K \leftarrow \min (K, a[i])$\;
}

这表明这在 O(n) 中完成。当然还有更多行的代码，我希望在那里也这样做。

Answer 1

您可以将其放在构造的中间线，并\smash与零宽度一起\makebox[0pt][l]确保它不会妨碍其他元素的水平对齐。

\documentclass{article}

\usepackage[ruled,vlined]{algorithm2e}

\begin{document}

\begin{algorithm}[H]
  \BlankLine
  $N \leftarrow a_1$\;
  $K \leftarrow a_1$\;
  \BlankLine
  \For{$i \leftarrow 2$ \KwTo $n$}{
      $N \leftarrow \max (N, a[i])$%
      \smash{\makebox[0pt][l]{$\qquad
        \left.\begin{array}{c}\strut\\\strut\\\strut\end{array}\right\} \mathcal{O}(n)$}}\;
      $K \leftarrow \min (K, a[i])$\;
  }
\end{algorithm}

\end{document}

如果元素数量为偶数，则需要将支架降低/升高到位：

\documentclass{article}

\usepackage[ruled,vlined]{algorithm2e}

\begin{document}

\begin{algorithm}[H]
  \BlankLine
  $N \leftarrow a_1$\;
  $K \leftarrow a_1$\;
  \BlankLine
  \For{$i \leftarrow 2$ \KwTo $n$}{
      $N \leftarrow \max (N, a[i])$\;
      $N \leftarrow \max (N, a[i])$%
      \raisebox{.5\baselineskip}[0pt][0pt]{\makebox[0pt][l]{$\qquad
        \left.\begin{array}{c}\strut\\\strut\\\strut\\\strut\end{array}\right\} \mathcal{O}(n)$}}\;
      $K \leftarrow \min (K, a[i])$\;
  }
\end{algorithm}

\end{document}

Answer 2

对此没有固定的惯例。我只是在选定的行中添加注释来解释为什么循环执行了那么多次。

请记住您的听众：如果他们是初学者，则需要比经验丰富的老手更多的细节。

也许最好的办法是只询问行号，并用文本逐行（范围）解释正在发生的事情，而不是污染算法的呈现。更重要的是，通常一系列行由循环一起执行，不需要单独的注释。更重要的是解释为什么循环重复多次。