복잡도 정의를 외웠는지가 아니라, Big-O로 후보를 좁히고 시간·메모리 사이를 끊는 판단력을 갖췄는지 보려는 질문이다.
시간 복잡도는 입력 크기 n이 커질 때 연산 횟수가 어떤 비율로 증가하는지 표현하고, 공간 복잡도는 추가로 쓰는 메모리의 증가율을 본다. Big-O 표기는 상수와 하위항을 떼고 성장률만 남겨 하드웨어와 무관하게 알고리즘을 비교하게 해 준다. 실무에서는 시간을 줄이려 메모이제이션·캐시로 메모리를 더 쓰거나, 메모리를 아끼느라 시간이 늘어나는 식으로 둘이 자주 충돌해서 한 축만 보면 잘못된 결정을 한다.
메모이제이션이나 캐시로 시간을 줄이고 메모리를 늘린 경험이 있다면 트레이드오프 사례로 연결할 수 있다
O(n²)에서 O(n log n)으로 바꿔 체감 성능이 확 달라진 경험이 있다면 성장률 차이와 엮을 수 있다
입력 크기 가정을 바꿨더니 알고리즘 선택이 달라진 경험이 있다면 평균·최악 시나리오 판단과 연결할 수 있다
아직 공개된 답변이 없어요. 첫 공개 답변을 남겨보세요.