简析大O表示法

説明する
アルゴリズム解析を行う場合、文全体の実行回数T(n)は問題規模nに関する関数であり、さらにT(n)のnに対する変化状況を分析し、T(n)の数量レベルを決定する.アルゴリズムの時間複雑度はT(n)＝O(f(n))と記す.問題の規模nの増加とともにアルゴリズム実行時間の成長率はf(n)の成長率と同じであり、アルゴリズムと呼ばれる漸近時間複雑度を時間複雑度と略称し、f(n)はnのある関数である.このように大文字でO()を使ってアルゴリズムの時間の複雑さを表現する表記を大O記法と呼びます.
二、導出方法

は、運転時間における加算定数のすべてを定数1で置換する.

は、修正後の運転回数関数において、最上位項目のみを保持する.

最高次項が存在し、かつ1でない場合、この項に乗算された定数が除去される.

三、実例

public void function ( int count) {
	for( int i = 0; i < count; i++ {
		System.out.print(i);
	}
}

public static void main(String[] args) {
	int a = 1;
	int b = 2
	int n = 3;
	function(n);
	for ( int i = 0; i < count; i++ {
		function(i);
	}

	for ( int i = 0; i < n; i++ ) {
		for ( j = i; j < n; j++) {
			System.out.print(j);
		}
	}
}

以上のコードの実行回数は、f(n)=3+n+n 2+n(n+1)/2=3/2*n 2+3/2 n+3の最終的な時間複雑度はO(n 2)です.
大O導出方法によると、第1ステップは3を1に変更することです.最高次数を保持するとき,最高次数はn 2であることが分かったので,このアルゴリズムの時間複雑さはO(n 2)であった.