빅오(Big-O)

입력값이 ∞을 향할때 함수의 상한을 설명하는 수학적 표기방법(시간복잡도 표시)

❗ 여기서 상한이란?

A: 함수가 가장 늦게 실행될 때를 의미한다. 최악/평균의 경우와 아무런 관계가 없다!!

종류

-O(1): 실행시간 일정.최고
ex) 해시 테이블의 조회 및 삽입

-O(logn): 매우 견고한 알고리즘
ex) 이진 검색

-O(n): 선형시간 알고리즘, 모든 입력값 적어도 1번 이상 찾기
ex) 비정렬 리스트에서 max/min 찾기

-O(nlogn): 비교 기반 정렬 알고리즘의 상한선
ex) 병합 정렬

❗ 단, 팀소트 정렬의 경우, 입력값이 최선일때 비교를 건너뛰어 O(n)에 처리가능

-O(n²): 비효율적 정렬 알고리즘
ex) 버블 정렬

-O(2ⁿ): 피보나치 수를 재귀로 계산하는 알고리즘

-O(n!): 가장 느린 알고리즘
ex) TSP(각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제)를 브루트 포스로 풀이할때(노가다)

알고리즘은 시간-공간 tradeoff관계(실행시간이 빠르면 공간을 많이 사용 or 공간을 적게 차지하면 실행시간이 느림)

분할상환분석

- 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도를 계산하는 방법
ex)동적 배열

병렬화(알고리즘 속도 UP)

-대표 장치= GPU : CPU보다 수백 배 더 많은 연산 동시에 수행 ㄱㄴ