시간 복잡도 분석 (Time complexity)

시간 복잡도란? - 입력 크기에 따라서 단위 연산이 몇 번 수행되는지 결정하는 절차 모든 경우 분석 (every-case analysis) - 복잡도는 입력 크기 n에만 종속되며, 입력 내용과는 무관하게 복잡도는 항상 일정함. - T(n)의 꼴로 표기함. - 예를 들어, 리스트 내 모든 값들의 합을 계산하는 경우, 단위 연산을 += 으로 정할 시 무조건 for문을 n번 실행하므로 시간 복잡도 T(n) = n 이다. 최악의 경우 분석 (worst-case analysis) - 복잡도는 입력 크기 n과 입력 값 모두에 종속됨. - 단위 연산이 수행되는 횟수가 최대, 즉 최악인 경우를 선택함. - W(n)의 꼴로 표기함. - 예를 들어, 길이가 n인 리스트 내에서 어떠한 수 y를 검색하는 경우, 단위 연산을 list[i] == y 라고 정할 시 최악의 경우 for문을 n번 수행하므로 W(n) = n 이다. 이 경우, 리스트의 값에 따라 검색하는 횟수가 달라지므로 모든 경우 분석은 불가능하...

원문링크 : 시간 복잡도 분석 (Time complexity)