search

j-jh-Study / technical-interview

스파르타 기술면접 스터디
0 stars 0 forks source link

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

Open J-Jaeh opened 1 year ago

J-Jaeh commented 1 year ago

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

J-Jaeh commented 1 year ago

시간복잡도

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

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

image

image

사진출처

J-Jaeh commented 1 year ago

알고리즘별,시간복잡도

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