
시간 복잡도
알고리즘/자료구조
2023. 4. 20. 14:03
시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 작성 방법에 따라 걸리는 시간이 달라지며, 시간이 적게 걸리는 것이 좋은 소스이다. 시간 복잡도에는 빅-오 표기법이라는 개념이 나온다. 예를 들어, 동전을 던져 뒷면이 나올 확률을 얘기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 던져야 하는 경우가 발생한다. 이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부른다. O(1) Constant Time (상수) 입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘. ..