big O
-
[시간 복잡도] 알고리즘 복잡도 표현 방법Algorithms & Data Structure 2022. 1. 18. 15:20
복잡도가 필요한 이유 하나의 문제를 푸는 다양한 방법이 있는데, 어떤 방법이 더 효율적인지 확인하기 위해 필요하다. 알고리즘 복잡도 계산 항목 시간 복잡도 : 알고리즘 실행 속도 공간 복잡도 : 알고리즘이 사용하는 메모리 공간 사이즈 공간 복잡도는 요즘 거의 사용하지 않는다. Big O 표기법 최악의 실행 시간을 표기. 가장 많이 사용하는 표기 방법이다. 최악의 상황이여도 이 정도 성능은 보장한다는 의미이다. 제일 큰 차원수만 표기한다. # O(1) : 무조건 상수만큼 실행 if n > 10: print(n) # O(n) variable = 1 for num in range(3): for index in range(n): print(index) # O( 𝑛2 ) : 300𝑛2 + 1도 결국 𝑛2 vari..