내일배움캠프 9일차 TIL + 자료구조와 알고리즘

오늘은 특별히 배웠다기 보다는 한번 옛날에 배운 내용을 다시 보면서 기록을 해보는 TIL 써보겠다.

알고리즘

Big O

Big O 는 자주쓰이는 알고리즘 시간복잡도 표현법으로 최고차항에 의해 흔히 결정된다.
간단히 말해서 해당 알고리즘이 가지는 최악의 경우 시간 복잡도를 수식으로 간단히 O(f(n))으로 나타낸다.

Sorting algorithm

Selection Sort

단순히 매번 배열을 돌면서 최소값을 맨앞으로 가져오는 경우
시간 : O(n^2)
공간 : O(1)

Insertion Sort

배열을 돌면서 맨앞에 정렬해두면서 각각 맞는 자리에 가져다 놓는 방식
시간 : O(n^2)
공간 : O(1)

Quick Sort

피벗을 두고 기준으로 그보다 작은애들과 큰애들을 분리해서 각각 정렬하는 방식
시간 : O(nlogn) ~ O(n^2)
공간 : O(log n) ~ O(n)

Merge Sort

반반으로 분리해서 각각 정렬하고 합치는 방식
시간 : O(nlogn)
공간 : O(n)

라이브러리 지원 Sort

당연히 대부분 언어가 Sort 를 지원하기에 sort 알고리즘을 짜서 쓸 일은 없다.

List<string> names = new List<string> ();
names.Sort();