알고리즘/이론 정리 (2) 썸네일형 리스트형 정렬 / 버블정렬 / 선택정렬 정렬은 말 그대로 무작위로 나열된 숫자들을 내림차순 또는 오름차순으로 정렬하는 방법이다. 정렬 방법은 다양하게 있는데 버블정렬과 선택정렬에 대해 정리해보려고 한다. 나만 그런지 모르겠는데 정렬 이름만 듣고 무슨 정렬인지 바로 떠오르지가 않고 자꾸 헷갈려서 이번에 정리하면서 기억해보려고 한다. 버블정렬 (bubble sort) 버블정렬은 인접한 두 수를 비교해서 정렬하는 방법이다. 정렬이 완료될 때까지 루프를 돌아서 정렬시킨다. 다음의 과정을 거친다. 1번째 루프 1. 5 10 7 22 4 위 배열을 오름차순 배열로 만들기 위해 0 ~ 4 번 숫자라고 했을 때 0번 자리 숫자부터 하나 큰 자리에 있는 숫자와 비교하여 정렬을 한다. 0번자리와 1번자리를 비교했을 때 5 < 10 이기 때문에 자리를 바꾸지 않.. 시간 복잡도 / Big-O 표기법 시간 복잡도 알고리즘을 만들고 그 알고리즘이 현실에서 사용가능한지 알아보기 위해 시간복잡도를 계산한다. 시간 복잡도(Time Complexity)는 입력의 개수가 n개일 때 알고리즘의 실행 시간을 n에 대한 함수로 표현한다. 최악의 경우 시간 복잡도는 입력의 개수가 n인 모든 가능한 입력에 대한 최대 실행 시간을 말한다. 보통 시간복잡도를 말할 때는 최악의 경우 시간복잡도를 의미한다. 알고리즘은 아주 n의 개수가 아주 많다고 가정하기 때문에 상수는 없는 것으로 취급하고 계수가 가장 큰 함수로 구한다. Big-O 표기법 상수 c와 n0가 존재하며, n≥n0 인 모든 n에 대하여 T(n) ≤ c · f(n)을 만족하면 T(n) = O(f(n))이라고 한다. T(n)=3n^2 + 100n 일 때, f(n)이 .. 이전 1 다음