한때 "Big-O 표기법은 무엇입니까?"라는 질문을 듣는 것보다 더 두려운 것이 없었습니다. 학교에서 배운 주제가 생각났지만 수학(내가 가장 잘하는 과목은 아니었음)과 관련이 있기 때문에 지워버렸습니다.
하지만 제 경력이 발전하면서 제 자신을 발견했습니다.
- 실적 차트 보기
- 느린 쿼리 디버깅 시도
- 부하가 증가할 때 내 코드가 어떻게 유지될지 고려했는지 묻는 메시지가 표시됨
Big-O를 배우기 위해 다시 원을 그리며(이해하셨나요?) 결정했을 때 저는 Big-O의 높은 수준의 단순성에 놀랐습니다. 이 기사에서 배운 내용을 공유하여 동료 엔지니어인 여러분이 멋진 인터뷰를 통과할 수 있을 뿐만 아니라 성능이 뛰어나고 확장 가능한 시스템을 구축할 수 있습니다.
약속합니다. Big-O는 보이는 것만큼 무섭지 않습니다. 일단 알고 나면 프로파일링 도구를 실행할 필요 없이 알고리즘을 보고 효율성을 쉽게 식별할 수 있습니다!
Big-O 표기법이란 무엇입니까?
Big-O 표기법은 "이 알고리즘의 최악의 경우 성능은 무엇입니까?"라고 말하는 멋진 방법입니다. O(n) 또는 O(1)로 설명된 함수를 본 적이 있을 것입니다. 이것은 다음을 의미합니다:
- O(n) - 최악의 경우 실행 시간은 입력 크기(n)가 증가함에 따라 선형적으로 증가합니다.
- O(1) - 최악의 경우 실행 시간은 모든 크기 입력에 대해 일정합니다.
...이것이 의미하는 바를 제대로 이해하려면 점근선에 대해 알아야 합니다.
점근선?
고등학교 대수학으로 돌아가 교과서에서 먼지를 털어내고 극한과 점근선에 관한 장을 펼쳐 보겠습니다.
- 한계 분석: 어떤 값에 접근할 때 함수에 어떤 일이 발생하는지 확인
- 점근적 분석: f(x)가 무한대에 접근할 때 어떤 일이 발생하는지 보기
예를 들어, 함수 f(x) =x^2 + 4x를 플로팅한다고 가정해 보겠습니다.
다음과 같은 분석을 수행할 수 있습니다.- 한계 분석: x가 증가함에 따라 f(x)는 무한대에 접근하므로 x가 무한대에 접근할 때 f(x) =x^2 + 4x의 극한은 무한대라고 말할 수 있습니다. - 점근적 분석: x가 매우 커질수록 4x 항은 x^2 항에 비해 무의미해집니다. 따라서 f(x) =x^2 + 4x는 x 값이 무한대에 접근하는 경우 f(x) =x^2와 거의 동일하다고 말할 수 있습니다.
<블록 인용>함수의 일부가 "무의미한" 상태가 되었다고 말할 수 있는 방법을 이해하려면 원래 함수에 다른 숫자를 연결할 때 어떤 일이 발생하는지 고려하십시오. 예를 들어 x =1일 때 함수는 1 + 4(5와 같음)를 반환합니다. 그러나 x =2,000일 때 함수는 4,000,000 + 8,000(4,008,000과 동일)을 반환합니다. x^2 항은 4x보다 총계에 훨씬 더 많이 기여합니다.
Big-O 표기법은 입력 크기가 변경됨에 따라 알고리즘의 런타임이 어떻게 변경되는지 설명하는 한 가지 방법입니다.
알고리즘의 실행 시간을 결정하는 것은 무엇입니까?
건초 더미에서 바늘을 찾는 데 얼마나 걸리냐고 묻는다면, 당신은 건초 더미에 얼마나 많은 건초가 있는지 알고 싶어할 것이라고 생각합니다. 내가 "10개"라고 답하면 1~2분 안에 바늘을 찾을 수 있다고 확신할 수 있지만 "1,000개"라고 말하면 아마 그렇게 흥분하지 않을 것입니다.
알아야 할 정보가 하나 더 있습니다. 추가된 각 건초 조각에 대한 스택을 검색하는 데 시간이 얼마나 걸립니까? 그리고 건초의 양이 무한대에 가까워지면 어떻게 될까요?
이것은 위의 점근적 분석의 예와 매우 유사합니다. 우리 모두가 이것을 이해했는지 확인하기 위해 하나의 예를 더 살펴보겠습니다. 함수 f(x) =5x^2 + 100x + 50을 고려하십시오. 이 함수의 두 부분을 별도로 그릴 수 있습니다.
이전 예와 마찬가지로 5x^2 항은 결국 100x + 50 항보다 커지므로 이를 삭제하고 f(x) =5x^2 + 100x + 50의 런타임이 x^2로 증가한다고 말할 수 있습니다.
물론 프로그램을 실행하는 실제 컴퓨터의 속도 및 사용된 언어와 같이 런타임에 영향을 미치는 다른 요소가 있다는 점을 언급할 가치가 있습니다.
선형 검색을 위한 Big-O 찾기
선형 탐색 알고리즘의 Big-O 분석을 해보자. 선형 검색은 데이터 세트의 시작 부분에서 시작하여 대상 요소를 찾을 때까지 탐색합니다.
다음은 Ruby에서 구현한 것입니다.
def find_number_via_linear_search(array, target)
counter = 0
# iterate through the given array starting
# at index 0 and continuing until the end
while counter < array.length
if array[counter] == target
# exit if target element found
return "linear search took: #{counter} iterations"
else
counter += 1
end
end
return "#{target} not found"
end
이 방법을 다음과 같이 사용할 수 있습니다.
# Let's create an array with 50 integers
# and then re-arrange the order to make
# things more interesting
array = [*1..50].shuffle
find_number_via_linear_search(array, 24)
나는 이것을 몇 번 실행했고 다음과 같은 결과를 얻었다:
=> "linear search took: 10 iterations"
=> "linear search took: 11 iterations"
=> "linear search took: 26 iterations"
함수의 Big-O 표기법을 분석할 때 우리는 최악의 상황을 고려합니다(일명 점근 상한).
이것을 직관적으로 생각하면 가장 작은 반복 횟수는 1입니다. 이는 대상 요소가 배열의 위치 0에 있을 때 발생합니다. 가장 큰 반복 횟수(또는 최악의 상황)는 50입니다. 이것은 대상 요소가 배열에서 발견되지 않을 때 발생합니다.
배열에 100개의 요소가 있는 경우 최악의 경우는 100회 반복됩니다. 200요소? 200회 반복. 따라서 선형 검색에 대한 Big-O 표기법은 단순히 O(n)이며, 여기서 n은 요소의 수입니다.
바이너리 검색을 사용한 더 복잡한 예!
다음으로 이진 검색을 고려해 보겠습니다. 다음은 사전 정렬된 배열:1. 중간 요소를 가져 가라.
2. element == target인 경우 우리는 끝났어3. element > target인 경우 배열의 위쪽 절반을 버립니다. 4. element < target인 경우 배열의 아래쪽 절반을 버리십시오. 5. 나머지 배열로 1단계부터 다시 시작하십시오.
참고:Rubyist라면 이 알고리즘을 구현하는 기본 제공 b-search 메서드가 있습니다!
예를 들어 사전이 있고 "파인애플"이라는 세계를 찾고 있다고 가정해 보겠습니다. 사전의 중간 페이지로 이동합니다. 세상에 "파인애플"이 생긴다면 우리는 끝났을 것입니다!
하지만 제 추측으로는 사전의 중간이 아직 "p"에 있지 않으므로 "llama"라는 단어를 찾을 수 있을 것입니다. 문자 "L"은 "P" 앞에 오기 때문에 사전의 아래쪽 절반 전체를 버립니다. 다음으로, 우리는 남은 것으로 과정을 반복할 것입니다.
선형 검색과 마찬가지로 이진 검색에 대한 최상의 실행 시간은 1회 반복입니다. 그러나 최악의 경우는 무엇입니까? 다음은 16개의 요소가 있는 배열의 예입니다. 이진 검색을 사용하여 숫자 23을 찾으려고 한다고 가정해 보겠습니다.
[2, 3, 15, 18, 22, 23, 24, 50, 65, 66, 88, 90, 92, 95, 100, 200]
첫 번째 단계는 인덱스 7의 숫자인 50을 살펴보는 것입니다. 50은 23보다 크므로 오른쪽에 있는 모든 것을 버립니다. 이제 배열은 다음과 같습니다.
[2, 3, 15, 18, 22, 23, 24, 50]
중간 요소는 이제 23보다 작은 18이므로 이번에는 아래쪽 절반을 버립니다.
[22, 23, 24, 50]
다음이 됩니다.
[22, 23]
결국
[23]
길이가 16인 배열에서 목표로 삼고 있는 숫자를 찾기 위해 총 4번 배열을 반으로 나누어야 했습니다.
이를 일반화하기 위해 이진 검색에 대한 최악의 상황은 배열을 반으로 나눌 수 있는 최대 횟수와 같다고 말할 수 있습니다.
수학에서 우리는 "저 숫자를 얻기 위해 이 숫자의 몇 개를 곱해야 합니까?"라는 질문에 답하기 위해 로그를 사용합니다. 문제에 대수를 적용하는 방법은 다음과 같습니다.
따라서 Big-O 또는 이진 검색에 대한 최악의 실행 시간은 log(base 2) n이라고 말할 수 있습니다.
마무리
Big-O 표기법은 "이봐, 최악의 경우가 뭐야?"라고 말하는 멋진 방법입니다. 컴퓨터 과학은 제쳐두고 실제 사례는 배관공에게 고장난 수도꼭지를 수리하는 데 비용이 얼마나 들냐고 물었을 때 일어나는 일입니다. 그는 "글쎄요, 2,000달러를 넘지 않을 것이라고 장담할 수 있습니다."라고 대답할 수 있습니다. 이것은 당신에게 별로 도움이 되지는 않지만 상한선입니다.
이 때문에 다른 Big-O 표기법이 자주 사용됩니다. 예를 들어, Big-Theta는 하한과 상한을 모두 고려합니다. 이 경우 배관공은 "글쎄요, $1,000 미만은 아니지만 $2,000를 넘지는 않을 것입니다."라고 대답할 것입니다. 이것은 훨씬 더 유용합니다.
읽어주셔서 감사합니다. 이 포스트가 Big-O 표기법을 조금 덜 무서운 주제로 만드는 데 도움이 되었기를 바랍니다!