알고리즘
- 알고리즘은 문제를 해결하기 위한 명확한 절차나 방법입니다.
- 알고리즘은 입력을 받아 원하는 출력을 생성하기 위한 절차입니다.
- 알고리즘은 입력, 출력, 명확한 단계, 실행 가능성의 특성을 갖습니다.
- 알고리즘은 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 합니다.
- 알고리즘은 컴퓨터 프로그래밍뿐만 아니라 다양한 분야에서 사용됩니다.
Big O 표기법
- Big O 표기법은 알고리즘의 효율성을 나타내는 표기법입니다.
- 특히, Big O 표기법은 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지를 설명합니다.
- Big O 표기법은 알고리즘의 최악의 경우 성능을 나타내므로 알고리즘의 효율성을 과장하지 않습니다.
표기법
- O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.
- O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다.
- O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.
- O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.
Big O 표기법 계산
- 상수 버리기
알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴봅니다. 상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버립니다. 예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있습니다.- 최고 차수 항목만 남기기
빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 따라서 가장 큰 차수의 항목만을 남기고 나머지는 버립니다. 예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있습니다.- 다항식의 경우 최고 차수 항목만 고려
다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 상수항이나 낮은 차수의 항목은 무시합니다. 예를 들어, O(3n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있습니다.- 연산자 상수 무시
빅오 표기법에서는 연산자나 상수 값을 무시합니다. 예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있습니다.
콜라게임