알고리즘(빅오, 자료형)

빅오

빅오 : 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구사항(공간 복잡도)이 어떻게 증가하는지를 분류할 때 사용, 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기방법.

점근적 실행시간 : 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 lim n->oo 함수의 실행 시간의 추이

• 빅오 : 상한
• 빅오메가 : 하한
• 빅세타 : 평균

분할 상환 분석

어느 자료 구조의 연산들의 임의의 시퀀스가 주어졌을 때, 그 시퀀스 위의 모든 연산들이 수행되는 동안 각 연산의 평균적인 수행시간을 분석하는 방법

자료형

• 불변 객체 : bool, int, float, tuple, str
• 가변 객체 : list, set, dict