TIL#80 PYTHON 기초(23)

정렬

• 리스트의 원소들을 특정 순서로 정리하는 것
• 정렬은 알고리즘의 기초
• 문제해결의 기초를 다질수 있음
• 모든 개발자가 알아야 하는 가장 기본적인 알고리즘

선택정렬 selection sort

• 각 위치에 어떤 값이 들어갈지 찾는다.
• 가장 먼저 생각날수 잇는 자연스러운 정렬 알고리즘
  (가장 작은 값을 찾아 0번 인덱스에 놓고, 두번째로 작은 값을 찾아 1번 인덱스에 놓고,
  세번째로 작은 값을 찾아서 2번 인덱스에 놓고...)

삽입정렬 insertion sort

• 각 값이 어떤 위치에 들어갈지 찾는다.

알고리즘 공부할때 신경써야 하는 것 - 시간, 공간

좋은 코드의
첫번째 기준 - 시간
두번째기준 - 공간( 컴퓨터의 저장공간 - 메모리)

🗒 컴퓨터 사양이나 여러가지 주변 상황의 영향을 받기 때문에 단순히 프로그램이 돌아가는 시간으로 알고리즘을 비교하는 것은 합리적이지 않음

시간복잡도
-> 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가 를 나타냄
-> 인풋 크기에 비례하는 알고리즘의 실행시간
공간복잡도
-> 인풋크기에 비례해서 알고리즘이 사용하는 메모리 공간

점근표기법(빅오)의 핵심
n이 크다고 가정(n이 별로 크지 않으면 안좋은 알고리즘을 써도 문제가 없기 때문)

선형탐색 알고리즘 O(n)
이진탐색 알고리즘 O(logn)

List operations

Operation	code	Average Case
인덱싱	list[index]	O(1)
정렬	list.sort() sorted(list)	O(nlogn)
뒤집기	list.reverse()	O(n)
탐색	element in list	O(n)
끝에 요소 추가	list.append(element)	O(1)
중간에 요소 추가	list.insert(index, element)	O(n)
삭제	del list[index]	O(n)
최솟값, 최댓값 찾기	min(list) max(list)	O(n)
길이 구하기	len(list)	O(1)
슬라이싱	list[a:b]	O(b-a)

Dictionary operations

Operation	Code	Average Case
값 찾기	dict[key]	O(1)
값 넣어주기/덮어쓰기	dict[key]=value	O(1)
값 삭제	del dict[key]	O(1)