[알고리즘] 시간복잡도와 공간복잡도

최근 CS 기술 면접 대비에 시간을 많이 쓰고 있다.
여러 자료 + 이전 강의에서 본 내용을 보면서 GPT와 모의면접을 하고 있는데, 생각보다 시간이 엄청 쓰인다.

이렇게 시간을 많이 쓰는데 면접이 끝나고, 붙으면 좋겠지만 혹여 떨어지면 지금 준비하는 이 시간이 아무것도 안한 시간이 될까봐. 
그리고 분명히 작년 11월 즈음 면접 준비를 하긴 했는데, 기억에서 날라가버렸다..
뭐라도 남겨보자는 심정과 노션에 흩어진 글을 조금이라도 정제해보자는 마음으로 이 포스팅을 시작하였다.

주로 GPT + VSFe 님의 기술면접 질문 모음집을 참고하였다.
질문과 답변 모두 신입 개발자의 입장에서 쓰여진 것이니 오류나 말이 안 맞는 것이 있을 수 있다. 혹은 더 좋은 답변이 있을 수 있다.
이를 발견하여 제게 알려주신다면 커피..라도 한잔 사드리고 싶을 것 같다. 🙇🏻‍♂️

시간복잡도와 공간복잡도에 대해 설명해 주세요.

시간복잡도란, 알고리즘이 수행되는데 걸리는 연산 횟수를 입력크기 n에 따라 수치화한 것입니다.

즉, 입력이 커질수록 알고리즘 실행 시간이 얼마나 늘어나는지를 표현합니다.

공간복잡도란 알고리즘이 실행되는 동안 추가로 사용하는 메모리 공간의 크기를 입력 크기에 따라 수치화한 것입니다.

왜 시간복잡도를 연산횟수로 설명할까요?

알고리즘의 실제 실행시간은 하드웨어, 언어, 환경에 따라 달라집니다.

따라서 절대적인 시간 대신, 입력 크기 n이 커질수록 얼마나 많은 연산을 수행하는지를 기준으로 알고리즘의 성능을 비교합니다.

보통 1초당 1억번 연산을 한다고 가정하고, n이 1000이면 O(n^2)까지 가능하구나, 100,000이면 O(nlogn)이하여야 하구나 판단합니다.

배열을 정렬하는 여러 알고리즘 중 퀵소트, 머지소트, 삽입 정렬의 시간 복잡도와 공간 복잡도를 비교해서 설명해주세요.

가능하다면 평균적인 경우, 최악의 경우, 공간 복잡도도 함께 이야기해주세요.

먼저 삽입정렬은 배열의 앞부분이 정렬되어있다 가정하고, 새로운 값을 앞에서부터 알맞은 위치에 삽입합니다.

개인적인 의견으로 삽입정렬의 경우 최선의 경우도 고려하면 좋을 것 같아 추가해보겠습니다.

머지소트는 배열을 재귀적으로 반으로 나눈 후, 각각을 정렬해서 합치는 방식입니다. 안정정렬입니다.

퀵소트는 하나의 값을 pivot으로 선택하고, 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 재귀적으로 정렬합니다.

pivot이 계속 가장 크거나 작으면 안족기에 pivot 선택 전략이 중요합니다. 안정정렬이 아닙니다.

                        평균                     최악                   최선              

삽입 정렬       O(n^2)                 O(n^2)              O(n)-이미 정렬된 경우 O(1)

머지소트        O(nlogn)              O(nlogn)           O(n)

퀵소트           O(nlogn)              O(n^2)              O(logn) ~ O(n)

 

정렬된 정도가 높고 작으면 삽입 정렬이 빠르고, 대용량 데이터에서는 메모리 이슈를 고려해 퀵소트가 선호되며, 안정성이 중요하면 머지소트를 고려해볼 수 있습니다.

Big-O, Big-Theta, Big-Omega 에 대해 설명해 주세요.

Big-O는 최악의 경우입니다. n이 클때, 최대로 얼마나 느린가 입니다.

Big-Omega는 최선의 경우입니다. 최소한 이정도는 걸린다는 하한선입니다.

Big-Theta는 정확한 성능 범위입니다. 상한 = 하한, 머지소트는 일정한 성능이 나오는 정렬입니다.

다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?

실행 시간이 가장 오래 걸릴 수 있는 상황을 기준으로 성능을 평가함으로써, 안정성과 예측 가능성을 확보할 수 있습니다.

보통 다른 기준은 입력의 모양에 대한 가정이 있지만, 현실에서는 예쁜 데이터는 보장되지 않습니다.

왜 Big-Θ는 실제로 잘 쓰이지 않을까?

최악과 최선, 평균이 비슷해야 사용 가능합니다. 하지만 대부분 알고리즘은 입력 형태에 따라 성능이 달라집니다.

Big-O 이외에 고려해야 할 실제 성능 요소가 있을까요?

1. 상수 계수퀵소트가 머지소트보다 빠른 이유는 상수항이 작기 때문이다.
2. 같은 O(nlogn)이더라도 내부 연산이 많아 현실 속도는 느릴 수 있다.
3. 캐시 친화성선형 접근 vs 랜덤 접근→ 선택보다 삽입이 좋을 수 있다. shift가 swap보다 근처에 있다.
4. → 배열 순회보다 연결 리스트 순회는 느리다. 같은 O(n)이어도.
5. 배열을 연속적으로 접근하면 CPU 캐시에 더 잘 맞아서 빠르다.
6. 실제 데이터 분포 특성
7. 삽입정렬은 O(n^2)이어도, 실제로 빠를 수 있다.
8. 언어별 특성자바스크립트는 재귀호출 시 콜스택 초과 위험이 있어 반복으로 구현
9. 파이썬은 재귀 깊이가 얕아서 퀵소트보다 머지소트 사용

어떤 상황에서는 삽입 정렬이 퀵소트나 머지소트보다 나을 수 있을까요?

데이터가 거의 정렬되어 있는 경우, 이미 정렬된 배열에 새로운 값 하나만 추가하면 되기에 O(n)으로 동작합니다. (내부 while문의 shift 연산할 필요 없음)

또 데이터 크기가 매우 작다면 (n < 32) 삽입 정렬은 함수 호출 오버헤드가 없고, 단순 루프라서 더 빠를 수 있습니다. 자바, 파이썬은 이를 하이브리드로 사용합니다.

마지막으로 메모리를 아껴야 한다면, in-place 정렬이라 유리할 수 있습니다.

O(1)은 O(N^2) 보다 무조건적으로 빠른가요?

아닐 수 있습니다.

예를 들어, 상수항이 크다면 - O(1)이지만 내부 if문이 많고, n=3인 O(n^2)은 연산횟수가 9번이면, 작은 n에서는 더 느릴 수 있습니다.

또는 캐시 적중률, 메모리 접근 방식, 재귀호출 오버헤드 등이 있스빈다.

메모리 배치 방식이 row-major order일 경우, 행 우선 접근은 메모리가 연속적이라 캐시 적중률이 높아 빠르고, 열 우선 접근은 캐시 미스라 느릴 수 있습니다.

메모리에서 한번에 불러오는 최소 단위 블록은 보통 64B이다. 이는 64비트 버스 * 8라인입니다.