알고리즘 정리

킴스코딩클럽·2022년 12월 5일
1

CS기초 시리즈

목록 보기
59/71
용어정리
공간복잡도
(space complexity)
프로그램에서 필요한 메모리 자원 공간의 양
시간복잡도
(time complexity)
프로그램이 수행하는 대입 이동 등의 연산들의 실행 횟수 여기에서 상수처럼 값이 변하지 않는 것은 무시되고 입력된 데이터만 고려됨
빅오(big 0)알고리즘 최적화에 크게 영향을 미치지 않는 부분을 무시해 간편하게 시간복잡도를 표기하는 방법
0(n^2)입력된 데이터값이 증가할 때 시간이 n의 제곱에 비례해 증가하는 복잡도를 가진 알고리즘
0(nlogn)분할 정복(conque÷)의 방식으로 탄생하게 된 병합 정렬에서 탄생한 방식으로 반으로 나누어 원소가 나눌 수 없을 때까지 반복하게되는 방식으로 logn을 n번 연산되는 방식
선택 정렬
(selection)
가장 큰 or작은 값을 찾아서 선택하고 맨 처음 또는 맨 끝부터 차례대로 넣어주는 방식 시간복잡도는 n^2 공간복잡도는 n
거품 정렬
(bubble)
바로옆의 데이터와 비교해 정렬하는 행동을 반복하는 방식
합병 정렬
(merge)
분할 정복(작은 단위로 쪼개서 해결하는 방식)을 사용하는 방식 nlogn의 시간복잡도와 n의 공간복잡도를 가짐 시간복잡도는 n^2 공간복잡도는 n
퀵 정렬
(quick)
분할 정복을 사용하는 방식으로 피벗값을 지정해 분할하는 과정을 추가함 평균적으로 nlogn의 시간 복잡도를 가지지만 최악의 상황에는n^2의 시간 복잡도를 가진다 공간복잡도는 n
profile
공부 기록용

0개의 댓글