[영상후기] 시간복잡도(time complexity)를 알차게 설명합니다! 빅 오(Big O)를 포함해서 점근적 표기법을 다양한 예제와 함께 설명하니까요 들러보세요~ :)

실행 시간(running time) : 함수/알고리즘 수행에 필요한 스텝(step) 수
-> 컴퓨터마다 성능 차이 등으로 정확한 실행 시간은 다르기에 간단하게 계산
-> 각 라인을 수행하기 위한 필요한 스텝 수는 상수(constant)라고 가정
-> input size가 증가할때가 궁금 --> 최고차항만 의미가 있음

점근적 분석 : 임의의 함수 N -> 무한대 일때 어떤 함수 형태에 근접해지는지 분석

시간 복잡도 : 함수의 실행 시간을 표현하는 것으로 주로 점근적 분석을 통해 실행 시간을 단순하게 표현(점근적 표기법으로 표현)

계산 : 최선/최악 케이스
1) 최선 케이스 : 0번째 존재(한번에) - 하한선 - 점근적 빅오메가(1)
2) 최악 케이스 : N번째 존재(제일 마지막) - 상한선 - 점근적 O(N)
--> 보통 최악케이스 의미 있게 봐서 빅오표기법 활용
3) 평균 케이스 : 최선 + 최악 / 2 => 상수 의미 없기에 최악과 동일 표기

세타로테이션 : 상한 = 하한일때 표기 가능 세타(1) 이런식

바이너리서치 : 정렬된 배열에서 타겟을 찾아 위치를 반환하는 서치
-> 가운데 부터 시작(가운데 값보다 크면 우측, 크면 좌측)
-> 매번 실행 시 사이즈가 1/2씩 줄어든다
-> N/2^k = 1 -> O(log2N)

성능 순서 : O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) M O(2^N) < O(N!)