면접카타 7일치

BIG O에 대해서 설명해 주세요

 

빅오 표기법은 알고르즘의 성능을 나타내는 방법 중 하나로 알고리즘의 시간 복잡도나 공간 복잡도를 표현할 떄 사용됩니다 이 표기법은 주로 최악의 경우를 기준으로 알고리즘의 실행 시간이나 필요한 메모리 공간이 이렵 크기에 대해 어떻게 증가하는지를 나타냅니다

 

빅 오 표기법의 기본적인 개념은 알고리즘의 효울성을 이해하고 비교하는 데 중요한 도구입니다 예를 들어 O는 알고리즘이 입력 크기 n에 비례하ㅣ여 시간이 증가함을 의미하며 O은 입력 크기와 상관없이 일정한 시간이 걸림을 나타냅니다 또한 o는 시간이나 공간이 입력 크기의 제곱에 비례하여 즈ㅇ가함을 의미합니다

 

다음은 몇 가지 일반적인 빅 오 표기법 예시입니다

 

• O(1): 상수 시간(complexity) — 입력 크기에 상관없이 알고리즘의 실행 시간이나 필요한 공간이 일정합니다.
• O(log n): 로그 시간(complexity) — 알고리즘이 실행될 때, 실행 시간이 입력 크기의 로그에 비례하여 증가합니다. 이는 일반적으로 매우 효율적인 성능을 의미합니다.
• O(n): 선형 시간(complexity) — 알고리즘의 실행 시간이나 필요한 공간이 입력 크기에 비례하여 증가합니다.
• O(n log n): 로그 선형 시간(complexity) — 많은 효율적인 정렬 알고리즘들이 이 카테고리에 속합니다.
• O(n²): 제곱 시간(complexity) — 알고리즘의 실행 시간이 입력 크기의 제곱에 비례하여 증가합니다. 크기가 큰 입력에 대해서는 비효율적일 수 있습니다