TIL#80 PYTHON 기초(23)

dnpxm387·2020년 10월 2일
0

python

목록 보기
39/42
post-thumbnail

정렬

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

선택정렬 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)|

profile
개발자꿈나무🌲

0개의 댓글