時間複雑度の解法

一部のプログラムの実行時間は正確な技術ではありません.通常、プログラムの実行回数をインストールして推定し、T(n)で表します.アルゴリズムの時間的複雑度を大文字Oで表し,アルゴリズムの時間的漸進的複雑度と呼ぶ.(1)時間的複雑度がO(1)の場合

		int i=3;    //  1 
		while（i<99） //  34 
		i=i+3;				//  33 

プログラムは69回実行され,実行回数が定数であればT(n)=O(1)である.(2)時間複雑度O(n)

	int i,s=0;			//  1 
	for(i=0;i<n;i++)	//  n+1 
	  s=s+1;			//  n 
	 prinf("%d",s);		//  1 

プログラムは2 n+3回実行され,最高レベルの項のみをとり,その係数を除くとT(n)=O(n)となる.(3)時間複雑度O(n 2)

	int i,j,s=0;			//  1 
	for(i=0;i<n;i++)		//  n+1 
		for(j=0;j<n;j++)	//  n(n+1) 
		s=s+1;				//  n^2 

プログラムは2 n 2+2 n+2回実行され,最高項を除去し,定数を除去するとT(n)=O(n 2)となる.(4)一般的な時間複雑度は定数次O(1),対数次O(log 2 n),線形次O(n),線形対数次O(nlog 2 n),平方次O(n 2),立方次O(n 3),・・・,k次方次O(nk)および指数次O(2 n)を数レベルで増分配列する.
参考書:データ構造(c言語版)