時間の複雑さの計算方法--およびその分析
2692 ワード
元のアドレス:http://www.nowamagic.net/librarys/veda/detail/2195
アルゴリズム解析を行う場合,文全体の実行回数T(n)は問題規模nに関する関数であり,さらにnに伴うT(n)の変化状況を解析し,T(n)の桁数を決定する.アルゴリズムの時間的複雑度、すなわちアルゴリズムの時間的メトリックは、T(n}=0(f(n))と記す.問題規模nの増大に伴い、アルゴリズム実行時間の埔長率はf(n)の埔長率と同じであり、アルゴリズムの漸近時間的複雑度と呼ばれ、時間的複雑度と略称される.ここでf(n)は問題ゲージ横nのある関数である.このようにアルゴリズムの時間的複雑さを大文字O()で表す記法を大O記法と呼ぶ.一般的にはnの増大に伴ってT(n)の成長が最も遅いアルゴリズムが最適アルゴリズムである. 以前に私たちが言った3つの求和アルゴリズムの時間複雑度はそれぞれ0(n),0(1),0(n 2)であった.私は押してみよう. 計算1+2+3+4+......+100.コードは以下の通りで、前にも述べたように: コードに添付された注釈から、すべてのコードが何回実行されているかがわかる.この書き込みコード文の実行回数の合計は、アルゴリズムが結果を算出するのに要する時間であると理解できる.このアルゴリズムにかかる時間(アルゴリズム文の実行総回数)は、1+(n+1)である+n+1=2 n+3でnが大きくなると、例えば、今回計算するのは1+2+3+4+......+100=?ではなく、1+2+3+4+......+n=?でnは非常に大きな数字であることから、上記のアルゴリズムの実行総回数(所要時間)nが大きくなるにつれて増加しますが、forサイクル以外の文はnの規模の影響を受けません(永遠に1回しか実行されません).したがって、上記のアルゴリズムの実行総回数を簡単に2 nまたは略記nと記すことができます.これにより、私たちが設計したアルゴリズムの時間的複雑さが得られ、O(n)と記すことができます.ガウスのアルゴリズムを見てみましょう: の導出方法を示した.運転時間中のすべての加算定数を定数1で置き換えます. 修正後の実行回数関数には、最も高い次数の項目のみが保持されます. 最上位アイテムが存在し、1でない場合、このアイテムに乗算された定数を除去します. ステップ3:「最上位の次数が存在し、かつ1でない場合、この項に乗じた定数を除去する」.ここでnの二次方程式は1ではないので、この項の乗数を除去するには、合計回数=n^2を実行するので、最後に上記のコードを得る計算時間の複雑さは、O(n^2)が上記のように「大O次」を導くの手順ではまず、「運転時間中のすべての加算定数を定数1で置き換える」という手順から、上記の式は、総回数=2 n^2+3 n+1を実行するステップとなり、「修正後の運転回数関数では、最上位次数項のみを保持する」という手順に変わります.ここでの最上位はnの2次方なので、計算式は、総回数=2 n^2 を実行することになります
アルゴリズム解析を行う場合,文全体の実行回数T(n)は問題規模nに関する関数であり,さらにnに伴うT(n)の変化状況を解析し,T(n)の桁数を決定する.アルゴリズムの時間的複雑度、すなわちアルゴリズムの時間的メトリックは、T(n}=0(f(n))と記す.問題規模nの増大に伴い、アルゴリズム実行時間の埔長率はf(n)の埔長率と同じであり、アルゴリズムの漸近時間的複雑度と呼ばれ、時間的複雑度と略称される.ここでf(n)は問題ゲージ横nのある関数である.
#include "stdio.h"
int main()
{
int i, sum = 0, n = 100; /* 1 */
for( i = 1; i <= n; i++) /* n+1 */
{
sum = sum + i; /* n */
//printf("%d
", sum);
}
printf("%d", sum); /* 1 */
}
#include "stdio.h"
int main()
{
int sum = 0, n = 100; /* 1 */
sum = (1 + n) * n/2; /* 1 */
printf("%d", sum); /* 1 */
}
#include "stdio.h"
int main()
{
int i, j, x = 0, sum = 0, n = 100; /* 1 */
for( i = 1; i <= n; i++)
{
sum = sum + i;
//printf("%d
", sum);
for( j = 1; j <= n; j++)
{
x++; /* n*n */
sum = sum + x;
}
}
printf("%d", sum); /* 1 */
}