Big-O notation
定義
ある関数$f(n)$と$g(n)$について,
$$
f(n) = O(g(n))
$$
であるとは,適当な定数$c,n_0\ge 0$が存在して,$\forall n\ge n_0$について
$$
f(n) \le c\cdot g(n)
$$
となることである.これを「$f(n)$のオーダーは$g(n)$である」という.
Big-O notation は次の性質を満たす.
\begin{align} {\mathbf 推移律:} & f(n) = O(g(n)), g(n) = O(h(n)) \Rightarrow f(n) = O(h(n)) \\ {\mathbf 和:} & O(f(n)) + O(f(n)) = O(f(n)) \\ {\mathbf 積:} & O(f(n))O(g(n)) = O(f(n)g(n)), \quad f(n)O(g(n)) = O(f(n)g(n)) \\ {\mathbf 定数倍:} & O(cf(n)) = O(f(n)) \quad (c\neq 0) \\ {\mathbf 冪等性:} & O\left(O(f(n))\right) = O(f(n)) \end{align}
一般的な証明
問いで与えられた隣接行列で実装したダイクストラ法を用いる単一始点最短経路問題を解くコードにおいて,比較/代入/四則演算の回数$f(N)$は
f(N) = N^2 + \cdots + N + \cdots + 1 \qquad {\rm (21個全部展開してください)}
である.ここで,適当な定数$c,N_0\ge 0$が存在して,$\forall N\ge N_0$について考えたときに,
\begin{align}
f(N) & = N^2 + \cdots + N + \cdots + 1\\
& \le c(N^2 + \cdots + N + \cdots + 1) \\
& \le cN^2 + \cdots + cN + \cdots + c \\
& \le cN^2 + \cdots + cN^2 + \cdots + cN^2 \\
& \le 21c\cdot N^2
\end{align}
となるから,Big-O notationの定義より$f(N)=O(N^2)$である.$\blacksquare$
ちょっと楽な証明
出していただいた画像から察するに,先ほどのように厳密な定理を使わずにそのままオーダー記法をしていいものとして書きます.
Big-O notationの和の性質から,
$$
O(N^2) + \cdots + O(N) + \cdots + O(1) = O(N^2)
$$
となるから,このコードの計算量は$O(N^2)$である.$\blacksquare$
屁理屈(だけどこのコードを見せられているならば正しい)証明
このコードは入力のサイズに依存しない(入力は探索開始地点しか受け取っていない)ため,定数時間で実行が終了する.よって計算量は$O(1)$.$\blacksquare$
余談
"厳密な記述が求められています"とのことでしたが,私にできる範囲はこれで限界です.厳密な証明は$\varepsilon - \delta$論法を用いて関数の極限を扱う形で証明が記述されますが,私は弊学にて上記に示した一般的な証明方法でしか習っておらず,力不足になります.
以上がよほどのガチ専門じゃない限りで満点がもらえそうな解答です(補償はできませんが).
そしてこの定義上,$f(N)$の計算量は$O(N^3)$でも$O(N^4)$でも$O(N^5)$でも$O(N^6)$でも正解です(でもhcictoryさんのテストで意図された答えではなさそうなのでバツをもらいそうです).
テスト頑張ってください.