시간 복잡도의 개념을 이해하면서 많은 학생들이 헷갈려하는데, 이번 글에서는 아주 간단한 예를 들어 설명하겠습니다.
Q. 100명의 학생이 있는 교실에서 한 사람에게 펜을 주었다고 상상해 보십시오. 누구에게 주었는지도 모른 채 그 펜을 찾아야 합니다.
다음은 펜을 찾는 몇 가지 방법과 O 순서가 무엇인지입니다.
- 에 2 ): 가서 반의 첫 번째 사람에게 펜이 있는지 물어보세요. 또한 이 사람에게 교실에 있는 다른 99명에게 그 펜 등이 있는지 물어보세요.
이것이 우리가 O(n이라고 부르는 것입니다.2). - 에): 학생 한명 한명 찾아가서 물어보는 것은 O(N)입니다.
- O(로그 n): 이제 나는 학급을 두 그룹으로 나누고 다음과 같이 질문합니다. 교실의 왼쪽에 있습니까, 아니면 오른쪽에 있습니까? 그런 다음 그 그룹을 두 개로 나누고 다시 묻는 식으로 진행됩니다. 펜을 가진 학생이 한 명 남을 때까지 이 과정을 반복하세요. 이것이 O(log n)의 의미입니다.
다음을 수행해야 할 수도 있습니다.
- 그만큼 에 2 ) 다음과 같은 경우 검색 어떤 학생에게 펜이 숨겨져 있는지 아는 학생은 단 한 명뿐입니다. .
- 그만큼 에) 만약에 한 학생이 펜을 가지고 있었는데 그들만이 그것을 알고 있었습니다 .
- 그만큼 O(로그 n) 검색해 보세요 학생들은 다 알고 있었어 , 그러나 내가 옳은 쪽을 추측한 경우에만 알려줄 것입니다.
위의 영형 -> 라고 한다 크다 – 아 이는 점근적 표기법입니다. 다른 것도 있습니다 점근 표기법 좋다 세타 그리고 오메가 .
메모: 우리는 프로그램 실행 중에 취해진 입력에 대한 시간 경과에 따른 증가율에 관심이 있습니다.
알고리즘/코드의 시간 복잡도는 코드의 실행/실행 시간과 동일합니까?
알고리즘/코드의 시간 복잡도는 다음과 같습니다. ~ 아니다 특정 코드를 실행하는 데 필요한 실제 시간과 동일하지만 명령문이 실행되는 횟수입니다. 우리는 이것을 이용하여 이것을 증명할 수 있다. 시간 명령 .
예를 들어: C/C++ 또는 기타 언어로 코드를 작성하여 N 숫자 사이의 최대값을 찾습니다. 여기서 N은 10, 100, 1000 및 10000입니다. Linux 기반 운영 체제(Fedora 또는 Ubuntu)의 경우 아래 명령을 사용합니다.
트리맵
프로그램을 컴파일하려면: gcc 프로그램.c – o 프로그램
프로그램을 실행하려면: 시간 ./프로그램
다음과 같은 놀라운 결과를 얻을 수 있습니다.
- N = 10인 경우: 0.5ms의 시간을 얻을 수 있습니다.
- N = 10,000인 경우: 0.2ms의 시간을 얻을 수 있습니다.
- 또한, 기계마다 타이밍이 다릅니다. 동일한 코드에 대해 동일한 시스템에서 동일한 타이밍을 얻지 못하더라도 그 이유는 현재 네트워크 부하 때문입니다.
그래서 우리는 다음과 같이 말할 수 있습니다. 코드를 실행하는 데 필요한 실제 시간은 기계에 따라 다릅니다. (Pentium 1을 사용하든 Pentium 5를 사용하든) 또한 컴퓨터가 LAN/WAN에 있는 경우 네트워크 로드도 고려합니다.
알고리즘의 시간 복잡도란 무엇을 의미합니까?
이제 시간 복잡도가 코드를 실행하는 데 필요한 실제 시간이 아니라면 문제가 발생합니다. 그러면 시간 복잡도는 무엇입니까?
정답은:
코드의 각 문을 실행하는 데 필요한 실제 시간을 측정하는 대신 시간 복잡도는 각 문이 실행되는 횟수를 고려합니다.
예시 1: 아래의 간단한 코드를 고려해보세요. Hello World를 인쇄하세요.
C++ #include using namespace std; int main() { cout << 'Hello World'; return 0; } // This code is contributed by vikash36905.> 씨 #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.> 파이썬3 print('Hello World') # This code is contributed by akashish__> 씨# using System; public class GFG{ static public void Main (){ // Code Console.WriteLine('Hello World'); } } // This code is contributed by lokesh> 자바스크립트 console.log('Hello World') // This code is contributed by nilha72xi.> 산출
Hello World>
시간 복잡도: 위 코드에서는 Hello World가 화면에 한 번만 인쇄됩니다.
따라서 시간복잡도는 상수: O(1) 즉, 사용 중인 운영 체제나 컴퓨터 구성에 관계없이 코드를 실행하는 데 일정한 시간이 필요할 때마다.
보조 공간 : ㅇ(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.> 씨 #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> 파이썬3 # Python code n = 8 for i in range(1, n + 1): print('Hello World !!!') # This code is contributed by lokesh> 씨# 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> 자바스크립트 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> 씨 #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> 파이썬3 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__> 씨# 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.> 자바스크립트 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 !!!>
시간 복잡도: 오(로그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> 씨 #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 !!!'); } } }> 파이썬3 n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hello World !!!') i *= i # 이 코드는 akashish__가 기여했습니다.> 씨# 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__> 자바스크립트 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(로그(로그 n))
보조 공간: 오(1)
알고리즘의 시간 복잡도를 찾는 방법은 무엇입니까?
이제 알고리즘의 시간 복잡도를 찾는 몇 가지 다른 예와 프로세스를 살펴보겠습니다.
예: 다음 사양을 가진 모델 기계를 고려해 보겠습니다.
- 단일 프로세서
- 32비트
- 순차적 실행
- 산술 및 논리 연산의 경우 1단위 시간
- 할당 및 반환문에 대한 1단위 시간
Q1. 위 기계에서 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< 씨 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__> 파이썬3 # Pseudocode : Sum(a, b) { return a + b } a = 5 b = 6 def sum(a,b): return a+b # function call print(sum(a,b))> 씨# // 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__> 자바스크립트 // 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 = 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__> 씨 Pseudocode : list_Sum(A, n) // A->배열 및 // n->배열의 요소 수 { sum = 0 for i = 0 ~ 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.> 파이썬3 # 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))>
씨# 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__> 자바스크립트 function list_Sum(A, n) // A->배열 및 // n->배열의 요소 수 { let sum = 0; for (나는 = 0이라고 하자; 나는<= 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 씨 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); } }> 파이썬3 def list_sum(A): sum = 0 for i in range(len(A)): sum = sum + A[i] return sum>
씨# 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); } }> 자바스크립트 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인 행렬 => Tsum = a.n 2 + b.n + c
- Tsum은 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__> 파이썬3 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>
씨# 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); } }> 자바스크립트 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>
시간 복잡도: 오(n*m)
프로그램은 두 개의 중첩 루프를 사용하여 2D 배열의 모든 요소를 반복합니다. 외부 루프는 n번 반복되고 내부 루프는 외부 루프가 반복될 때마다 m번 반복됩니다. 따라서 프로그램의 시간복잡도는 O(n*m)이다.
보조 공간: 오(n*m)
프로그램은 고정된 양의 보조 공간을 사용하여 2D 배열과 몇 가지 정수 변수를 저장합니다. 2D 배열에 필요한 공간은 nm 정수입니다. 또한 프로그램은 단일 정수 변수를 사용하여 요소의 합계를 저장합니다. 따라서 프로그램의 보조 공간 복잡도는 O(nm + 1)이며 이는 O(n*m)으로 단순화됩니다.
결론적으로 프로그램의 시간 복잡도는 O(nm)이고, 보조 공간 복잡도도 O(nm)이다.
따라서 위의 예에서 입력을 사용하여 수행하는 작업 유형에 따라 실행 시간이 증가한다는 결론을 내릴 수 있습니다.
알고리즘을 비교하는 방법?
알고리즘을 비교하기 위해 몇 가지 객관적인 척도를 정의해 보겠습니다.
- 실행 시간: 실행 시간은 특정 컴퓨터에 따라 다르므로 좋은 측정 방법은 아닙니다.
- 실행된 명령문 수: 명령문의 수는 프로그래밍 언어와 개별 프로그래머의 스타일에 따라 다르기 때문에 좋은 척도는 아닙니다.
- 이상적인 솔루션: 주어진 알고리즘의 실행 시간을 입력 크기 n(즉, f(n))의 함수로 표현하고 실행 시간에 해당하는 이러한 다양한 함수를 비교한다고 가정해 보겠습니다. 이러한 종류의 비교는 기계 시간, 프로그래밍 스타일 등과 무관합니다.
따라서 이상적인 솔루션을 사용하여 알고리즘을 비교할 수 있습니다.
관련 기사:
- 시간 복잡도와 공간 복잡도
- 알고리즘 분석 | 세트 1(점근적 분석)
- 알고리즘 분석 | 세트 2(최악, 평균, 최선의 경우)
- 알고리즘 분석 | 세트 3(점근적 표기법)
- 알고리즘 분석 | 세트 4(루프 분석)
- 알고리즘 분석 | 세트 5(상각분석 소개)
- 시간 복잡도의 기타 문제
- 시간 복잡도 분석 연습 문제
- 경쟁 프로그래밍의 복잡성 알기