목록계산복잡도 (1)
개발박사가 되고싶은 척척학사
[알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도
계산복잡도 : 어떤 알고리즘이 문제를 풀기위해 해야하는 계산이 얼마나 복잡한지를 나타낸 정도를 말한다. 즉, 알고리즘의 성능, 효율을 측정하기 위한 것이다. 계산 복잡도는 특별한 언급이 없다면 시간 복잡도를 의미하는 것이지만 본래 계산 복잡도는 시간 복잡도(time complexity), 공간 복잡도(space complexity)로 두가지가 있다. 계산 복잡도를 표현하는 방법에는 여러가지가 있는데 그 중 대표적인 표기법은 대문자 O 표기법(Big-O 표기법) 이다. 시간 복잡도 : 어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석한 것. O(n) : 알고리즘에 필요한 연산 횟수가 입력 크기 n과 비례할 때. O(1) : 알고리즘에 필요한 연산 횟수가 입력 크기 n과 무관할 때. 예를 들어 ..
Algorithm
2020. 2. 11. 23:20