빅오! 예제를 통한 시간 복잡성

훌륭한 개발자가 다양한 알고리즘 중에서 선택하는 동안 가장 먼저 고려하는 것은 실행하는 데 걸리는 시간과 필요한 공간입니다. 이 기사에서는 시간 복잡성을 고려하는 것이 왜 중요한지 그리고 몇 가지 일반적인 시간 복잡성이 무엇인지에 대해 이야기 할 것입니다.

실행 시간이 왜 그렇게 중요한가요?

Google지도의 예를 들어, A에서 B까지 가능한 한 빨리가는 최단 경로를 원할 것입니다. 또는 데이터 분석의 경우 가능한 한 빨리 분석이 수행되기를 원할 것입니다. 따라서 최적의 시간 내에 알고리즘에서 원하는 결과를 얻기 위해 시간 복잡성을 고려합니다.

시간 복잡성을 측정하는 방법

절대 시간을 측정합니까?

아니요, 알고리즘 단계 수와 입력 크기를 고려합니다.

따라서 시간 복잡도는 주어진 수의 입력 (n)을 가진 알고리즘이 작업을 완료하는 데 걸리는 시간을 분석하는 단순화 된 수학적 방법입니다. 입력은 어떤 크기라도 될 수 있지만 일반적으로 큰 입력 크기에 관심이 있으므로 몇 가지 근사치를 작성합니다. 즉,’n’증가하는 동안 가장 큰 영향을 미치는 표현식의 요소 만 고려합니다. 이것을 점근 분석이라고합니다.

알고리즘의 실행 시간 복잡도를 계산하는 데 사용되는 세 가지 유형의 점근 표기법이 있습니다.

1) 빅오

2) 빅 오메가

3) 빅 세타

빅 오메가 표기법 (Ω) :

인수가 특정 값이나 무한대를 향하는 경향이있을 때 함수의 제한 동작을 설명합니다. 알고리즘 실행 시간의 하한을 알려줍니다. 알고리즘이 완료하는 데 걸리는 최적의 경우 또는 최적의 시간을 측정합니다.

예 : Ω (n²) 실행 시간 복잡도를 갖는 알고리즘이 있으며, 알고리즘이 Ω (n) 또는 Ω (log n) 또는 Ω (1) 시간 복잡도를 갖는 것도 사실입니다.

Big Theta 표기법 (θ) :

인수가 특정 값이나 무한대를 향하는 경향이있을 때 함수의 제한 동작을 설명합니다. 알고리즘 실행 시간의 하한과 상한을 모두 알려줍니다.

Big-O 표기 :

인수가 특정 값이나 무한대를 향하는 경향이있을 때 함수의 제한 동작을 설명합니다. 알고리즘 실행 시간의 상한을 알려줍니다. 알고리즘이 완료하는 데 걸릴 수있는 최악의 경우 또는 가장 긴 시간을 측정합니다.

예 : 시간 복잡도로 O (n²)를 갖는 알고리즘이 있고, 알고리즘이 O (n³) 또는 O (n⁴) 또는 O (n⁵) 시간 복잡도를 갖는 것도 사실입니다.

이 기사에서는 Big-O 표기법에 초점을 맞출 것입니다. Big-O 표기법이 무엇인지 이미 논의했습니다. 이제 Big-O 표기법에 설명 된 일반적인 시간 복잡성이 무엇인지 논의하겠습니다.

위의 표는 Big-O 표기법을 사용하여 표현 된 가장 일반적인 시간 복잡도를 보여줍니다. 이러한 일반적인 시간 복잡성을 하나씩 살펴 보겠습니다.

1) 상수 시간 [O (1)] :

알고리즘이 입력 크기에 의존하지 않는 경우 일정한 시간 복잡도가 있다고합니다.

예를 들어 두 개의 숫자를 바꿔야 할 때

다른 예는 숫자가 홀수인지 짝수인지 확인해야하는 경우입니다. 이 모든 예에서 시간 복잡도는 입력 크기와 무관하므로 O (1)입니다.

2) 대수 시간 [O (log n)] :

각 단계에서 입력 크기가 줄어들면 알고리즘은 대수 시간 복잡도를 갖는다 고합니다. 로그 시간 복잡도의 일반적인 예는 이진 검색입니다. 우리가 알고 있듯이 이진 검색 트리는 정렬되거나 정렬 된 트리입니다. 왼쪽 노드는 항상 오른쪽 노드보다 작은 숫자입니다.

정렬 된 목록에서 요소의 위치를 ​​찾아야하는 이진 검색의 예를 들어 보겠습니다.

여기에서 각 단계에서 입력 크기를 두 부분으로 나누고 있음을 코드에서 볼 수 있으므로 여기서 시간 복잡도는 O (log n)라고 결론을 내릴 수 있습니다.

3) 선형 시간 [O (n)] :

시간 복잡도가 입력 크기에 따라 선형 적으로 증가하면 알고리즘은 선형 시간 복잡도를 가져야합니다. 알고리즘이 있고 항목을 정렬하는 데 걸리는 시간을 계산하고 있다고 가정합니다.

정렬 할 항목 수

위의 표에서 볼 수 있듯이 입력 크기와 소요 시간 사이의 관계는 선형 적이므로 위의 알고리즘은 선형 시간 복잡도를 갖는다 고 말할 수 있습니다.

예를 들어, 정렬되지 않은 목록을 고려하고 목록에서 최대 수를 찾으려고합니다.

이 예에서는 list의 모든 값을 살펴보고 숫자가 ‘maximum’변수에 저장된 이전 숫자보다 큰지 확인해야합니다. 따라서 목록의 각 값을 검색하면 ‘for’루프를 사용하여 각 숫자에 대해 동일한 작업을 반복하므로 O (n)의 시간 복잡성이 발생합니다. 그리고 for 루프 내부에서는 조건이 참인지 한 번만 확인하는 것이기 때문에 시간 복잡도는 O (1)입니다. 따라서 전체 시간 복잡도는 O (n)이됩니다.

4) 준 선형 시간 [O (n log n)] :

입력 데이터의 각 연산이 로그 시간 복잡도를 가질 때 알고리즘은 준 선형 시간 복잡도를 갖는다 고합니다.

각 입력이 O (1) 시간 복잡도를 가지므로’n’입력에 대해 O (n) 시간 복잡도가 발생하는 선형 복잡도와 마찬가지로이를 선형 시간 복잡도와 비교할 수 있습니다. 마찬가지로 여기에서 각 입력에는 O (log n)가 있고 이러한’n’입력이 있으므로 결과 시간 복잡도는 O (n log n)입니다.

준 선형 시간 복잡성은 병합 정렬, 퀵 정렬 및 힙 정렬과 같은 정렬 알고리즘에서 일반적입니다.

5) 2 차 시간 [O (n²)] :

알고리즘이 ‘n’입력이있는 입력 데이터의 각 값에 대해 O (n) 시간 복잡도를 갖는 선형 연산을 수행하면 2 차 시간 복잡도가 있다고합니다.

예를 들어 중첩 된 ‘for’루프가있을 때마다 시간 복잡도가 2 차 시간 복잡도가 될 것이라고 말할 수 있습니다. 목록의 각 값에 대한 모든 값을 반복하여 O (n) * O (n) 즉, O (n²) 시간 복잡도를 만들기 때문입니다.

2 차 시간 복잡성의 몇 가지 예는 버블 정렬, 삽입 정렬 등입니다.

6) 지수 시간 [O (c ^ n)] :

이‘c’는 상수입니다. 우리 기사에서 c = 2를 고려해 봅시다. 따라서 시간 복잡도는 O (2 ^ n)가됩니다.

알고리즘에 필요한 시간이 두 배가되면 시간이 기하 급수적으로 복잡하다고합니다.

지수 적 시간 복잡도에 대한 몇 가지 예는 피보나치 수 계산, 동적 프로그래밍으로 여행하는 세일즈맨 문제 해결 등입니다.

피보나치 수를 계산하기 위해 우리는 재귀 함수를 사용합니다. 이는 함수가 함수에서 자신을 호출 함을 의미합니다. 따라서 시간 복잡도는 함수가 자신을 호출하는 횟수와 함수의 시간 복잡도에 따라 달라집니다.

7) 요인 [O (n!)] :

알고리즘이 입력 크기에 따라 계승 방식으로 성장하면 알고리즘에 계승 시간 복잡성이 있다고 말할 수 있습니다.

간단한 예는 주어진 숫자의 계승을 찾는 것입니다.

Big-O 표기법을 사용하여 알고리즘을 분석하는 방법

이제 알고리즘의 시간 복잡성을 분석하는 동안 우리는 세 가지 사례, 즉 최상의 사례, 최악의 경우 및 평균 사례를 이해해야합니다.

이러한 경우를 이해하기 위해 정수 [12, 6, 2, 8, -5, 22, 0]의 1 차원 배열의 예를 들어 보겠습니다. 우리의 임무는 주어진 배열에서 지정된 숫자를 검색하는 것입니다.

이 예에서 가장 좋은 경우는 검색해야하는 숫자가 배열의 첫 번째 숫자 인 12 일 때입니다. 숫자가 인덱스 0에 있기 때문에 숫자는 한 번의 반복에서 발견됩니다. 최적의 시나리오는 배열에서 숫자를 검색하는 데 최소한의 시간이 필요하므로 O (1)의 최적 시간 복잡성을 제공합니다.

위에 언급 된 예에서 최악의 경우는 검색 할 숫자가 배열의 끝에있는 경우입니다. 즉, 주어진 예에서 숫자 0을 검색하는 경우입니다.

여기서 숫자 0은 인덱스 6에 있으며이를 찾으려면 전체 배열을 탐색해야합니다. 따라서 알고리즘은 배열에서 숫자를 검색하는 데 가장 오랜 시간이 걸리므로 시간 복잡성이 증가합니다. O (n)은 시간 복잡도가됩니다.

검색 할 숫자가 주어진 배열에없는 경우 또 다른 최악의 시나리오가있을 수 있습니다.

여기서 평균 사례는 검색 할 숫자가 배열의 중간에있는 경우입니다. 즉, 위의 예에서는 8이됩니다. 그러면 알고리즘이 8을 검색하는 데 평균 시간이 걸립니다. 정렬. 이 경우 알고리즘이 수행하는 단계의 수는 n / 2이지만 점근 분석을 수행 할 때 O (n)의 시간 복잡도를 고려합니다.

결론

위의 관찰에서 우리는 O (1), O (log n) 및 O (n)과 같은 시간 복잡도를 갖는 알고리즘이 빠른 것으로 간주된다고 말할 수 있습니다. 반면, 시간 복잡도가 O (n log n) 인 알고리즘도 빠르다고 간주 할 수 있지만 O (n²), O (c ^ n) 및 O (n!)과 같은 O (n log n) 이상의 시간 복잡도는 다음과 같습니다. 느린 것으로 간주됩니다. 따라서 O (n log n)이 임계 값처럼 작동한다고 말할 수 있습니다. 그 이상의 시간 복잡도는 그 아래의 복잡도보다 느립니다.

물론 복잡한 문제를 해결하려고 할 때이를 해결할 수있는 수백 가지 방법이 있습니다. 그래서 여기서 요점은‘옳다’,‘틀리다’가 아니라‘좋다’‘나쁘다’입니다. 따라서 코드를 작성할 때마다 시간의 복잡성을 고려하면 장기적으로 유익 할 것입니다.

이 게시물을 재미있게 읽고 그로부터 무언가를 배웠기를 바랍니다. 이것은 나의 첫 번째 게시물입니다. 이 주제로 시작하고 싶었습니다. 학사 과정 중에도 시간 복잡성 개념과이를 구현하는 방법 및 위치를 이해하는 데 어려움을 겪었 기 때문입니다. 수년 동안 연습을 통해 저는 개념에 대해 확신을 갖게되었으며이 게시물을 통해 모든 사람이 그렇게하도록 권장합니다.