TIL 27 알고리즘

알고리즘
문제를 해결하기 위한 단계적인 방법

- 알고리즘

- Big O 표기법

입력의 크기에 따라 알고리즘이 얼마나 많으 시간이나 공간을 필요로 하는지를 설명합니다.

• O(1) : 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.

• O(n) : 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다

• O(n^2) : 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.

• O(log n) : 로그 시간. 입력 크기의 로그에 비례하여 시간이 걸립니다.

  - big O 표기법 계산

• 1. 상수 버리기
     알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴봅니다.
     상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버립니다.
     예를 들어, O(2n), O(3n^2)같은 경우 O(n), O(n^2)로 간소화할 수 있습니다.
• 2. 최고 차수 항목만 남기기
     빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춥니다.
     따라서 가장 큰 차수의 항목만을 남기고 나머지는 버립니다.
     예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있습니다.
• 3. 다항식의 경우 최고 차수 항목만 고려
     다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춥니다.
     상수항이나 낮은 차수의 항목은 무시합니다.
     예를 들어, O(n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있습니다.
• 4. 연산자 상수 무시
     빅오 표기법에서는 연산자나 상수 값을 무시합니다.
     예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있습니다.

  공간 복잡도

• 코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라,
  입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명합니다.