- 완벽하게 똑같은 코드는 없음
-> 어떤 코드가 좋은 코드냐?에 대한 기준이 필요함
-> 복잡도를 정의해서 비교함
- 시간 복잡도는 알고리즘의 실행 속도
공간 복잡도는 알고리즘이 사용하는 메모리 사이즈
-> 사실상 시간 복잡도로 알고리즘을 평가하는 경우가 많음
- 시간 복잡도는 반복문이 지배함
- 보통은 빅오 표기법을 많이 씀
-> 빅오 표기법은 최악의 실행 시간을 표기함
-> 즉, 최악의 상황이라도 이 정도의 성능을 보장한다는 것임
- 만약 시간 복잡도 함수가 2n2 + 3n이라면?
-> 시간 복잡도는 O(n2)
- 1부터 n까지의 합은
-> for문을 써서 계산할 수도 있고, (n+1)*n/2로 계산할 수 있음
-> 전자는 O(n), 후자는 O(1)
-> 후자가 더 효율적이라고 할 수 있음
- 참고
한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online편