jinyux https://blog.hatena.ne.jp/jinyux/ jinyux’s diary https://jinyux.hatenablog.com/ 計算量のO表記はなんとなく理解はしていたが、厳密な定義がわかってなくてもやもやしてたので少しまとめる。アルゴリズムの実行時間は各々の環境によって変わってくるので、コンピュータが実行する命令の数を実行時間とする。また正確な命令の数を把握するのは困難であるので漸近記法またはビッグオー記法で実行時間を見積もる。それらの記法の定義を以下に示す。 極限の定義とちょっと似ている。ある関数に対してが十分大きいとき、を満たすが存在するならばはに属すると言う。ちょっと複雑な関数が具体的に与えられたとき、この関数を単純化して表したい。そのときにをより単純であろうで表すための記法である。例えばに属するのは、以下であ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjinyux.hatenablog.com%2Fentry%2F2022%2F06%2F20%2F000000" title="計算量の表記について - jinyux’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2022-06-20 00:00:00 rich https://jinyux.hatenablog.com/entry/2022/06/20/000000 1.0 100%