初めまして日本で就活している韓国人、
真面目な開発者 シム ドンモクです。
今日はアルゴリズムを勉強する時よく見るビッグ・オー記法について勉強します。難しい部分は勉強する時反感をそそるので私が考えるときアルゴリズムを勉強する時必要な部分だけ説明します。
ビッグ・オー記法とは、アルゴリズムの性能を数学的に表記する表記法です。アルゴリズムの効率を考える時は時間や空間で考えますが殆ど時間を中心として考えます。別に空間について書いてない場合は時間を中心として考えたと思ってもいいです。ここで話しているアルゴリズムの性能は簡単に言うとアルゴリズムの速さです。即ち、アルゴリズムの性能が良いと言うとアルゴリズムの速さが速いと同じ意味です。
アルゴリズムの速さ = 入力の値がnの場合の演算の回数
もっと詳しく説明するとビッグ・オー記法でビッグ・オーとは簡単に説明すると”最悪の場合でもこのぐらいです”と思っても十分です。例えばバブルソートをビッグ・オー記法で書くとO(n^2)です。即ち、バブルソートで入力の値がnの場合、最悪の場合n^2の時間が掛かるの意味です。このぐらいならビッグ・オー記法について説明は十分だと思います。
しかし！もうちょっと説明すると次に勉強するバブルソートを例で説明するとバブルソートの演算回数を等差数列の一般項によって説明するとn*(n+1)/2ですがバブルソートをビッグ・オー記法で表現するとO(n*(n+1)/2)ではなくてO(n^2)です。
理由はビッグ・オー記法で入力の値nがめっちゃデカイ数の場合足し算、割り算など計数は意味が無くなります。そして大事なことは次数です。
それで+1, /2は表現しなくてn^2で表現する事です。
ここまでがビッグ・オー記法の基本的な説明でした。これから色んなソートアルゴリズムを勉強しながらもしビッグ・オー記法について必要な説明があると説明する予定です。有難う御座います。
もしビッグ・オー記法について韓国語の説明が必要な方がいらっしゃると
https://blog.naver.com/dmjack私の韓国のブログですご覧ください。