파이썬 알고리즘 인터뷰 - 빅오 정리본
알고리즘(Algorithm)
알고리즘이란 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법이다.
계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정 순서를 의미한다. (위키피아 참조)
알고리즘이란 컴퓨터를 통해 구현되고 컴퓨터(cpu성능에 따라 차이는 나겠지만)는 굉장히 복잡한 연산처리도 빠르게 계산을 한다. 그러므로 아무리 복잡한 알고리즘이라도 입력 값이 작으면 금방 끝나버린다.
따라서 입력 값이 충분히클 때 알고리즘의 효율성에 따라 수행시간이 크게 차이가 날 것 이다.
그 효율성(알고리즘의 성능)을 시간복잡도와 공간 복잡도로 나타내며
빅오(big-o)는 시간복잡도, 공간복잡도를 표기하는데 쓰인다.
빅오(big-O)
빅오(O, big-O)란 입력값이 무한대(∞)로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다.
점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법(점근표기법) 중 하나이다.
점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력 값이 무한대(∞)를 향할 때 실행 시간의 추이를 의미한다.
달리 말하면 시간 복잡도라 할 수 있다.
시간복잡도
시간 복잡도(Time complexity)는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(효율성)을 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 빅오(O, big-O)이다.
빅오로 시간 복잡도를 표현 할때는 최고차항만을 표기한다.
예를 들어 4n²+3n+4번만큼 계산하는 함수(알고리즘)가 있다면 최고차항인 4n²에서 계수를 무시하며n²만을 고려한다. 즉 예시의 시간복잡도는 O(n²)로 나타낸다.
✍️ 실행시간 추이에 따른 빅오 표기법 종류
O(1)
입력값이 아무리커도 실행 시간이 일정한(상수의 시간)을 같는 알고리즘이다.
최고의 알고리즘이라 할 수 있으나 상수 값이 매우 크다면 사실상 의미가 없다.
따라서 최고의 알고리즘이 될 수 있으나 그 만큼 신중해야한다.
O(1)로 실행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당한다.O(log n)
로그는 매우 큰 입력값에도 크게 영향을 받지 않는다. 따라서 웬만한 n(입력값)의 크기에도 매우 견고하다.
대표적으로 이진검색이 이에 해당한다.O(n)
선형시간(Linear-Time) 알고리즘이라고 한다. 수행시간이 입력값에 비례하며
정렬되지 않은 리스트에서 최댓값, 최솟값을 찾는 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한번 이상은 살펴봐야 한다O(n log n)
병합정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다.
적어도 한번 이상은 비교하는 기반 정렬 알고리즘[O(n)]은 아무리 좋은 알고리즘 이라도 O(nlog n)보다 느리다.
(입력값이 최선인 경우 비교를 건너뛰어 O(n)이 더 빠를 수 있다. 팀소트(Timesort)가 이에 해당)O(n²)
버블 정렬 같은 비효율적인 정렬 알고리즘이 이에 해당한다.
O(2ⁿ)
피보나치수를 재귀로 계산하는 알고리즘이 이에 해당한다.
n²와 처음은 비슷하지만 훨씬 더 크다.O(n!)
각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(Travelling Salesman Problem(TSP)를 브루트 포스로 풀이할 때가 이에 해당한다.
가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항식 내에서 계산이 어렵다.
시간복잡도 vs 공간복잡도
시간 복잡도와 공간 복잡도는 반비례 관계이다.
실행 시간이 빠른 알고리즘은 공간을 많이 차지하며 또한 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다.
(드물지만 실행 시간이 빠르면서 공간을 적게 차지하는 알고리즘도 있음)
상한 vs 최악
빅오 표기법은 정확하게 쓰기엔 너무 길고 복잡한 함수를 '적당히 정확하게'표현하는 방법이다.
따라서 최악,평균,최선의 시간 복잡도와 연관성이 없다.
최악은 동일한 알고리즘, 같은 문제의 크기 에서 입력값에 따라 바뀌는 연산 시간 중 최악을 나타낸다.
퀵 정렬의 로무토 파티션(가장 우측 피벗 선택)에서
최선의 경우)
입력값 = [1, 4, 4, 7, 8, 6, 5]일 때, 18번 연산(O(n log n))최악의 경우)
입력값 = [1, 2, 3, 4, 5, 6, 7]일 때, 42번 연산
빅오(O)는 상한을 의미한다. 이외에도 하한을 나타내는 빅오메가(Ω) 평균을 나타내는 빅세타(θ)가 있다
가장 빨리 실행되는 알고리즘을 하한, 빅오메가(Ω)
가장 늦게 실행 되는 알고리즘을 상한, 빅오(O) 로 지칭한다.
빅오 표기법은 n이 작은 경우는 무시하며 n이 매우 클 때의 전체적인 큰 그림을에 집중한다.
🤔 그럼 상한, 하한은 큰그림 최악, 최선은 그 세부사항인가?
음 파이썬 알고리즘 인터뷰를 정리한 내용이지만 맞는 것 같은데 아직 헷갈린다... 아닌 것 같기도하고... 지금은 이해 불가... 개념이 다시 정립되었을 때 다시 정리하자...
분할 상환 분석
알고리즘의 복잡도를 계산할 때, 알고리즘의 전체를 보지 않고 최악의 경우만을 살펴보는 것은 지나치게 비관적이라는 이유로 분활 상환 분석 방법이 등장하게 되었다.
분활 상환 분석은 빅오와 함께 함수의 동작을 설명할 때의 중요한 분석 방법 중 하나이다.
분활 상환 분석의 대표적인 예로 '동적배열'이 있는데, 동적배열에서 더블링이 일어나는 경우는 간혹 있는 경우이지만, 이로인해 '아이템 삽입 시 시간복잡도는 O(n)이다'라는 것은 비관적이며 정확하지 않다. 따라서 이 최악의 경우를 여러 번에 걸쳐 나눠주는 형태(분활 상환)으로 시간 복잡도를 계산한다. 이럴 경우 동적 배열의 삽입 시 시간복잡도는 O(1)이다..
🤔 동적배열이란?
크기를 지정하지 않고 자동으로 리사이징하는 배열로 파이썬에서는 리스트가 해당한다.
미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 다 차면 , 늘려주고 모두 복사하는 방식이다.
대개는 더블링(Doubling)이라 하여 2배씩 늘려주게 되는데, 모든 언어가 항상 그런 것은 아니며 각 언어마나 늘려가는 비율은 상이하다.
분활 상환 분석은 1985년 미국의 수학자이자 컴퓨터과학자인 로버트 타잔(Robert Tarjan)이 [상각된 계산 복잡도(Amortized Computational Complexity)]라는 논문에서 처음으로 소개 되었으며 시간복잡도를 분석할 때 매우 보편적으로 사용되는 방법이다.
병렬화
일부 알고리즘은 병렬화로 실행 속도를 높일 수 있다.
GPU는 병렬 연산을 위한 대표적인 장치이다.
알고리즘이 병렬화 가능한지는 근래의 알고리즘의 우수성을 평가하는 매우 중요한 척도 중 하나이다.
파이썬 알고리즘 인터뷰 정리본
정확하게 정립이 안된 부분) 상한, 최악 -> 나중에 수정.
