O(1): 지속적으로 효율적

지난 포스트에서 우리는 O(n) 일명 선형 시간을 분해했습니다. 왜냐하면 (제 생각에는) O(n)은 이해하기 가장 간단하고 일반적인 복잡성이기 때문입니다. n(입력 수/크기)이 증가함에 따라 O(작업 수)도 비슷한 비율로 증가합니다.

진실은 훨씬 더 단순한 공통 복잡성이 있다는 것입니다. 뿐만 아니라 가장 효율적입니다.

물론 O(1) 또는 상수 시간에 대해 이야기하고 있습니다.

케이터링 회사로 돌아가기

지난 시간을 기억한다면 행사를 위해 케이터링 회사를 고용했습니다. 우리는 모두를 위한 개별 접시를 만들기로 결정했고 따라서 케이터링 알고리즘을 O(n)으로 계산했습니다.

하지만 모든 사람을 위해 개별 접시를 만들 필요가 없다면 어떨까요?

대신 큰 수프 냄비 하나만 만들면 어떨까요!

그러면 우리는 하루 종일 아무것도 할 필요가 없을 것입니다! 우리는 거대한 수프 냄비 하나를 만들고 모든 손님에게 충분히 큰 수프를 만들 수 있습니다.

이전과 마찬가지로 의사 코드를 작성해 보겠습니다.

# n = number of guests

def cater_party (n)
   # make 1 big pot of soup
end

그렇다면 입력 크기와 관련하여 작업 수가 어떻게 증가합니까?

손님이 1명이면 국 1솥을 끓입니다.
손님이 100명이면 국 1솥을 끓입니다.
손님이 10억이면 국 1솥을 끓입니다.

우리의 알고리즘을 보고 논리적으로 생각해 보면 얼마나 많은 사람들이 우리 행사에 참석하든 상관없이 우리는 여전히 수프 한 냄비만 만들 것입니다.

우리의 경우 작업 수는 일정합니다. 우리 알고리즘은 단순히 입력에 따라 복잡성이 증가하지 않습니다.



big-o 표기법을 단순화하기 위해 상수 값을 1로 단순화할 수 있음을 기억하십시오(상수 값이 복잡성에 미치는 영향은 더 높은 n 값에서 무시할 수 있을 정도로 감소하기 때문입니다). 실제로 얼마나 많은 작업이 수행되더라도 입력 크기와 함께 증가하지 않으면 하나의 큰 작업으로 간주할 수 있습니다.

그래서 우리는 O(1)을 얻습니다.

가장 효율적인 복잡성

O(1) 알고리즘은 시간이 일정하기 때문에 가장 효율적인 복잡성입니다. 진정으로 일정한 시간 알고는 무한한 양의 데이터를 처리할 것입니다.

아마도 사용한 적이 있는 코드 예제는 인덱스로 배열 요소에 액세스하는 것입니다. 이 경우 인덱스를 알고 있으므로 프로그램이 요소의 위치를 ​​정확히 알고 있기 때문에 배열의 크기는 중요하지 않습니다.

복잡도가 O(1)인 다른 많은 알고리즘이 있으며 다른 많은 복잡한 알고리즘에서 이를 사용합니다. 실제로 대부분의 기본 작업은 O(1) 복잡성을 가진 알고리즘으로 생각할 수 있습니다.

다음번

이제 O(n)과 O(1)을 살펴보았으므로 더 복잡해지기 시작할 것입니다.