時間計算量の概念を理解しながら混乱する学生も多いですが、この記事では非常に簡単な例で説明します。
Q. 100 人の生徒がいる教室で、1 人にペンを渡したところを想像してください。誰に贈ったのか分からないまま、そのペンを見つけなければなりません。
ここでは、ペンを見つける方法と、O の順序について説明します。
- の上 2 ): あなたはクラスの最初の人にペンを持っているかどうか尋ねに行きます。また、この人に、教室にいる他の 99 人について、そのペンを持っているかどうかなどを尋ねると、
これを O(n2）。 - の上）： 生徒一人ひとりに個別に聞きに行くのは O(N) です。
- O(log n): 次に、クラスを 2 つのグループに分けて、「教室の左側にいますか、それとも右側にいますか?」と尋ねます。次に、そのグループを 2 つに分け、再度質問するということを繰り返します。自分のペンを持っている生徒が 1 人になるまで、このプロセスを繰り返します。これが O(log n) の意味です。
次のことを行う必要があるかもしれません:
- の の上 2 ) 次の場合に検索します どの生徒にペンが隠されているかを知っているのは 1 人の生徒だけです 。
- の の上） もし ある生徒がペンを持っていましたが、それを知っていたのは彼らだけでした 。
- の O(log n) 検索する 生徒たちはみんな知っていた 、ただし、右側を推測した場合のみ教えてくれます。
上記 ○ -> と呼ばれます ビッグ – ああ これは漸近表記です。他にもあります 漸近表記 のように シータ そして オメガ 。
注記： プログラムの実行中に取得される入力に関する時間の経過に伴う増加率に興味があります。
アルゴリズム/コードの時間計算量はコードの実行/実行時間と同じですか?
アルゴリズム/コードの時間計算量は次のとおりです。 ない これは、特定のコードの実行に必要な実際の時間と同じですが、ステートメントが実行される回数です。これを次を使用して証明できます。 時間コマンド 。
例えば： C/C++ またはその他の言語でコードを作成し、N 個の数値の最大値を見つけます。N は 10、100、1000、10000 の範囲で変化します。 Linux ベースのオペレーティング システム (Fedora または Ubuntu) の場合は、次のコマンドを使用します。
通常形
プログラムをコンパイルするには: gcc プログラム.c – o プログラム
プログラムを実行するには: 時間/プログラム
次のような驚くべき結果が得られます。
- N = 10 の場合: 0.5 ミリ秒の時間が得られる可能性があります。
- N = 10,000 の場合: 0.2 ミリ秒の時間が得られる可能性があります。
- また、マシンごとに異なるタイミングが得られます。同じマシン上で同じコードに対して同じタイミングが得られない場合でも、その背後にある理由は現在のネットワーク負荷です。
したがって、次のように言えます。 コードの実行に実際に必要な時間はマシンによって異なります （Pentium 1 または Pentium 5 を使用しているかどうか）また、マシンが LAN/WAN にある場合はネットワーク負荷も考慮されます。
アルゴリズムの時間計算量とは何を意味しますか?
ここで、時間計算量がコードの実行に必要な実際の時間ではない場合、時間計算量とは何でしょうか?という疑問が生じます。
答えは次のとおりです。
コード内の各ステートメントの実行に必要な実際の時間を測定する代わりに、 時間計算量では、各ステートメントが実行される回数が考慮されます。
例 1: 以下の簡単なコードを考えてみましょう。 ハローワールドを印刷する
文字列のJava値C++
#include using namespace std; int main() { cout << 'Hello World'; return 0; } // This code is contributed by vikash36905.> C #include int main() { printf('Hello World'); return 0; }> ジャワ import java.io.*; class GFG { public static void main(String[] args) { System.out.print('Hello World'); } } // This code is contributed by vikash36905.> Python3 print('Hello World') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code Console.WriteLine('Hello World'); } } // This code is contributed by lokesh> JavaScript console.log('Hello World') // This code is contributed by nilha72xi.> 出力
Hello World>
時間計算量: 上記のコードでは、Hello World が画面に 1 回だけ表示されます。
したがって、時間計算量は次のようになります。 定数: O(1) つまり、使用しているオペレーティング システムやマシン構成に関係なく、コードの実行には毎回一定の時間がかかります。
補助スペース :O(1)
例 2:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i++) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by vikash36905.> C #include void main() { int i, n = 8; for (i = 1; i <= n; i++) { printf('Hello World !!!
'); } }> ジャワ class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { System.out.printf('Hello World !!!
'); } } } // This code is contributed by Rajput-Ji> Python3 # Python code n = 8 for i in range(1, n + 1): print('Hello World !!!') # This code is contributed by lokesh> C# using System; public class GFG { public static void Main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { Console.Write('Hello World !!!
'); } } } // This code contributed by Rajput-Ji> JavaScript let i, n = 8; for (i = 1; i <= n; i++) { console.log('Hello World !!!'); }> 出力
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
時間計算量: 上記のコードでは Hello World !!!印刷のみです n回 n の値は変更される可能性があるため、画面上で確認できます。
したがって、時間計算量は次のようになります。 線形: O(n) つまり、コードの実行には毎回直線的な時間がかかります。
補助スペース: ○(1)
例 3:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include void main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> ジャワ class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i=i*2) { System.out.println('Hello World !!!'); } } } // This code is contributed by Suruchi Kumari> Python3 n = 8 # for (i = 1; i <= n; i=i*2) { for i in range(1, n+1, 2): print('Hello World !!!') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code int i, n = 8; for (i = 1; i <= n; i=i*2) { Console.Write('Hello World !!!
'); } } } // This code is contributed by lokeshmvs21.> JavaScript for (i = 1; i <= 8; i=i*2) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> 出力
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
時間計算量: O(ログ2(n))
補助スペース: ○(1)
例 4:
C++ #include #include using namespace std; int main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include #include void main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> ジャワ import java.lang.Math; class GFG { public static void main(String args[]){ int i, n = 8; for (i = 2; i <= n; i=(int)Math.pow(i,2)) { System.out.println('Hello World !!!'); } } }> Python3 n = 8 i = 2 for j in range(2,n+1): if(i>= n): Break print('Hello World !!!') i *= i # このコードは akashish__ によって提供されています> C# using System; using System.Collections.Generic; public class GFG { static public void Main() { int i, n = 8; for (i = 2; i <= n; i = (int)Math.Pow(i, 2)) { Console.WriteLine('Hello World !!!'); } } } // This code is contributed by akashish__> JavaScript for (let i = 2; i <= 8; i=Math.pow(i,2)) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> 出力
Hello World !!! Hello World !!!>
時間計算量: O(log(log n))
補助スペース: ○(1)
アルゴリズムの時間計算量を調べるには?
次に、アルゴリズムの時間計算量を見つけるための他の例とプロセスを見てみましょう。
例： 次の仕様を持つモデル マシンを考えてみましょう。
- シングルプロセッサ
- 32ビット
- 順次実行
- 算術および論理演算の 1 単位時間
- assign ステートメントと return ステートメントの 1 単位時間
Q1.上記のマシンで 2 つの数値の合計を求めます。
どのマシンでも、2 つの数値を加算する擬似コードは次のようになります。
C++ // Pseudocode : Sum(a, b) { return a + b } #include using namespace std; int sum(int a,int b) { return a+b; } int main() { int a = 5, b = 6; cout< C Pseudocode : Sum(a, b) { return a + b }> ジャワ // Pseudocode : Sum(a, b) { return a + b } import java.io.*; class GFG { public static int sum(int a, int b) { return a + b; } public static void main(String[] args) { int a = 5, b = 6; System.out.println(sum(a, b)); } } // This code is contributed by akashish__> Python3 # Pseudocode : Sum(a, b) { return a + b } a = 5 b = 6 def sum(a,b): return a+b # function call print(sum(a,b))> C# // Pseudocode : Sum(a, b) { return a + b } using System; public class GFG { public static int sum(int a, int b) { return a + b; } static public void Main() { int a = 5, b = 6; Console.WriteLine(sum(a, b)); } } // This code is contributed by akashish__> JavaScript // Pseudocode : Sum(a, b) { return a + b } function sum(a, b) { return a + b; } let a = 5, b = 6; console.log(sum(a, b)); // This code is contributed by akashish__> 出力
11>
時間計算量:
- 上記のコードには 2 単位の時間 (定数) がかかります。
- 1 つは算術演算用で、もう 1 つは算術演算用です。
- 返品用に1つ。 (上記の規則に従って)。
- したがって、合計演算を実行するための総コスト ( ) = 1 + 1 = 2
- 時間計算量 = O(2) = O(1) 、2は定数なので
補助スペース: ○(1)
Q2.リスト/配列のすべての要素の合計を求める
これを行うための擬似コードは次のように指定できます。
C++ #include using namespace std; int list_Sum(int A[], int n) // A->配列と // n->配列内の要素の数 { int sum = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } int main() { int A[] = { 5, 6, 1, 2 }; int n = sizeof(A) / sizeof(A[0]); cout << list_Sum(A, n); return 0; } // This code is contributed by akashish__> C Pseudocode : list_Sum(A, n) // A->配列と // n->配列の要素数 { sum = 0 for i = 0 to n-1 sum = sum + A[i] return sum }>> ジャワ // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->配列と // n->配列内の要素の数 { int sum = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } public static void main(String[] args) { int[] A = { 5, 6, 1, 2 }; int n = A.length; System.out.println(list_Sum(A, n)); } } // This code is contributed by lokeshmvs21.> Python3 # A function to calculate the sum of the elements in an array def list_sum(A, n): sum = 0 for i in range(n): sum += A[i] return sum # A sample array A = [5, 6, 1, 2] # Finding the number of elements in the array n = len(A) # Call the function and print the result print(list_sum(A, n))>
C# using System; public class GFG { public static int list_Sum(int[] A, int n) // A->配列と // n->配列内の要素の数 { int sum = 0; for (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } static public void Main() { int[] A = { 5, 6, 1, 2 }; int n = A.Length; Console.WriteLine(list_Sum(A, n)); } } // This code is contributed by akashish__> JavaScript function list_Sum(A, n) // A->配列と // n->配列内の要素の数 { let sum = 0; for (i = 0 とする; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } let A = [ 5, 6, 1, 2 ]; let n = A.length; console.log(list_Sum(A, n)); // This code is contributed by akashish__> 出力
14>
上記のコードの時間計算量を理解するために、各ステートメントにどれくらいの時間がかかるかを見てみましょう。
int list_Sum(int A[], int n) { int sum = 0; // cost=1 no of times=1 for(int i=0; i C Pseudocode : list_Sum(A, n) { total =0 // cost=1 no of times=1 for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the end false condition) sum = sum + A[i] // cost=2 no of times=n return sum // cost=1 no of times=1 }> ジャワ public class ListSum { // Function to calculate the sum of elements in an array static int listSum(int[] A, int n) { int sum = 0; // Cost = 1, executed 1 time for (int i = 0; i < n; i++) { // Cost = 2, executed n+1 times (+1 for // the end false condition) sum = sum + A[i]; // Cost = 2, executed n times } return sum; // Cost = 1, executed 1 time } // Main method for testing public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5}; int length = array.length; int result = listSum(array, length); System.out.println('Sum: ' + result); } }> Python3 def list_sum(A): sum = 0 for i in range(len(A)): sum = sum + A[i] return sum>
C# using System; class Program { // Function to calculate the sum of elements in a list static int ListSum(int[] A) { int sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (int i = 0; i < A.Length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Driver code static void Main() { // Example usage int[] array = { 1, 2, 3, 4, 5 }; int result = ListSum(array); Console.WriteLine(result); } }> JavaScript function listSum(A) { let sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (let i = 0; i < A.length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Example usage let array = [1, 2, 3, 4, 5]; let result = listSum(array); console.log(result);> したがって、合計演算を実行するための総コストは
合計=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
したがって、上記のコードの時間計算量は次のようになります。 の上）
Q3.行列のすべての要素の合計を求める
この場合、複雑さは多項式 (正方行列の二次方程式) です。
- サイズ n*n の行列 => ツム＝あ・ん 2 + b.n + c
- ツムはn順なので2、 したがって 時間計算量 = O(n 2 )
#include using namespace std; int main() { int n = 3; int m = 3; int arr[][3] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } cout << sum << endl; return 0; } // contributed by akashish__> ジャワ /*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { int n = 3; int m = 3; int arr[][] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } System.out.println(sum); } } // akashish__> Python3 n = 3 m = 3 arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]] sum = 0 # Iterating over all 1-D arrays in 2-D array for i in range(n): # Printing all elements in ith 1-D array for j in range(m): # Printing jth element of ith row sum += arr[i][j] print(sum) # This code id contributed by shivhack999>
C# using System; class MainClass { static void Main(string[] args) { int n = 3; int m = 3; int[, ] arr = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i, j]; } } Console.WriteLine(sum); } }> JavaScript let n = 3; let m = 3; let arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]]; let sum = 0; // Iterating over all 1-D arrays in 2-D array for (let i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (let j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } console.log(sum);> 出力
43>
時間計算量: O(n*m)
プログラムは、2 つのネストされたループを使用して、2D 配列内のすべての要素を反復処理します。外側のループの反復ごとに、外側のループは n 回反復され、内側のループは m 回反復されます。したがって、プログラムの時間計算量は O(n*m) です。
選択範囲の並べ替え
補助スペース: O(n*m)
プログラムは、2D 配列といくつかの整変数を格納するために固定量の補助スペースを使用します。 2D 配列に必要なスペースは nm 個の整数です。また、プログラムは単一の整変数を使用して要素の合計を保存します。したがって、プログラムの補助空間の複雑さは O(nm + 1) であり、単純化すると O(n*m) になります。
結論として、プログラムの時間計算量は O(nm)、補助空間計算量も O(nm) です。
したがって、上記の例から、入力を使用して行う操作の種類に応じて実行時間が増加すると結論付けることができます。
アルゴリズムを比較するにはどうすればよいですか?
アルゴリズムを比較するために、いくつかの客観的な尺度を定義しましょう。
- 実行時間: 実行時間は特定のコンピュータに固有であるため、適切な尺度ではありません。
- 実行されたステートメントの数: ステートメントの数はプログラミング言語や個々のプログラマのスタイルによって異なるため、これは良い尺度ではありません。
- 理想的な解決策: 与えられたアルゴリズムの実行時間を入力サイズ n (つまり f(n)) の関数として表現し、実行時間に対応するこれらの異なる関数を比較すると仮定します。この種の比較は、マシン時間やプログラミング スタイルなどとは無関係です。
したがって、理想的なソリューションを使用してアルゴリズムを比較できます。
関連記事：
- 時間の複雑さと空間の複雑さ
- アルゴリズムの分析 |セット 1 (漸近分析)
- アルゴリズムの分析 |セット 2 (最悪のケース、平均的なケース、最良のケース)
- アルゴリズムの分析 |セット 3 (漸近記法)
- アルゴリズムの分析 |セット 4 (ループの分析)
- アルゴリズムの解析 |セット 5 (償却分析の概要)
- 時間計算量のその他の問題
- 時間計算量解析に関する練習問題
- 競技プログラミングの複雑さを知る