Q-시간복잡도,공간복잡도

[J-Jaeh]

알고리즘에서 '시간복잡도'와 '공간복잡도'란 무엇인가? 그리고 이것들은 왜 중요한가?

[J-Jaeh]

시간복잡도

함수의 실행 시간을 표한한것, 주로 점근적 분석을 통해 실행시간을 단순하게 표현하며 이때 점근적 표기법으로 표현

상한선을 가지고 표현해야함 아무리 느려도 ~ 이정도는 넘어서지 않는다가 중요
즉 O(N) <-> 오메가(1)

사진출처

[J-Jaeh]

알고리즘별,시간복잡도

O(1) : 스택에서 푸쉬 팝 같은거
O(lonN) : 이진트리 (로그의 지수가 2)
O(N) : for 완전루프
O(N*longN) : 퀵정렬, 병합정렬, 힙정렬
O(N^2) : 이중for문 , 삽입정렬, 버블정렬, 선택정렬
O(2^n) : 피보나치수