코딩인터뷰 완전분석 (VI big-O 예제 8)

 

이 글은 [코딩인터뷰 완전분석]을 읽고 정리한 글입니다.

 

작성일: 2024-01-22

수정일: 

 

독서 기간: 2024-01-22 ~ 😮

 

기본 환경

☕Java

 

📖

깊이우선탐색과 너비우선탐색을 하다가 멈춰버린 알고리즘..

근본을 찾아 틈틈이 읽어보려고 했는데, 분량이 어마어마합니다. 880페이지..😮

우선 파이팅..!

---

문제

여러 개의 문자열로 구성된 배열이 주어졌을 때 각각의 문자열을 먼저 정렬하고 그 다음에 전체 문자열을 사전순으로 정렬하는 알고리즘의 수행시간

 

 

해설

- 가장 긴 문자열의 길이: s

- 배열의 길이: a

 

1. 각 문자열을 정렬하는 데 걸리는 시간: O(slogs)

    * 이진탐색 기준: 총 글자수 * 파티션 글자수

    * logs: 데이터가 s개 일 때, logs 단계만에 원하는 데이터를 찾을 수 있음

2. a개의 문자열 정렬하는 데 걸리는 시간: O(a* slogs)

3. 전체 문자열을 사전순으로 정렬하는 데 걸리는 시간

    3.1. 문자열 전체 비교: O(aloga)

    3.2. 문자열 2개를 비교: O(s)

        * 각 문자열을 비교하는 데 걸리는 시간은 문자열의 길이 s에 비례

    3.3. 총 소요시간: O(s*aloga)

4. 전체 시간 복잡도: O(a*s(loga + logs))

 

 

⭐ 중요

역할이 다른 변수는 다른 이름으로 지정, 모두 N으로 선언해서는 안됨