cre_chan https://blog.hatena.ne.jp/cre_chan/ ミケ猫の小部屋 https://cre-chan.hatenablog.com/ 皆さん、久しぶり！競プロを始めてから実装の話ばかりしていた。いよいよアルゴリズムの原点に戻った！今回は例のを見に行きたいと思う。 この級数はどこで出るの？ まずは結論から言うと、この級数はクラスに属す。これでちょっと見覚えがあるのか？セットを使って配列から重複を取るアルゴリズムは配列の要素を順に見て行き、そしてセットにいるかどうかをチェックする。配列の長さをNとして、セットのサイズをKとする。クエリごとの時間がかかる。その結果、全体の計算量はこの級数になる。 その他にもLIS問題、最短経路問題など超有名問題で出てくる大人気級数である。 いきなり現れるは一体なんだ？ 授業ではビッグOを教えること… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fcre-chan.hatenablog.com%2Fentry%2F2021%2F02%2F17%2F025728" title="よく出るあの級数！情報系なら絶対覚えるべき計算量の話！ - ミケ猫の小部屋" 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 2021-02-17 02:57:28 rich https://cre-chan.hatenablog.com/entry/2021/02/17/025728 1.0 100%