現実のコードでの計算量の「1」はどれくらいの大きさか - 計算量の「1」の再確認 - Progate Tech Blog
こんにちは、Progate で新規事業開発のテックリードをしている 島津(@MakotoShimazu) です。 この4月に入社 してから半年以上経ち、重い腰をあげてようやく Progate のテックブログデビューしました。皆さんよろしくおねがいします。 ※ 本記事は Progate Advent Calendar 3日目の記事になります。 計算量といえば、少し前にちょっとした話題になったのを覚えている方も多いのではないでしょうか。 100日後に退職する47歳90日目#100日後に退職する47歳 pic.twitter.com/QqVgmonX7q - 元アプリ開発者47歳@100日後に退職する47歳 (@tome_ura) 2021年10月13日 しかし、学生さんなどに実際に計算量を数えてもらおうとすると、しばしば何を数えればよいのかわからない、つまり「1」の決め方で混乱している人を見かけます。 そこで本記事では、時間計算量における「1」とは何者なのかを振り返ってみようと思います。 (そして、もしやる気がでたら、もう一歩踏み込んで実際のコードを見ながら「1」の時間について考えてみようと思います。) 時間計算量は、ある処理における計算時間を見積もるための値です。 Time complexity - Wikipedia なんかを見てみると、以下のように書いてあります。 Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.