자료구조 및 알고리즘 요약정리 - 2

01-2-8 강의

1. 순차탐색알고리즘과 이진탐색 알고리즘 비교

순차탐색: T(n)=n -> O(n)

이진탐색: T(n)=log2n+1 -> O(logn)

 

=> 

 

2. T(n)=log2n -> O(logn)인 이유(왜 밑수 2를 고려하지 않는가?)

이때 1/(logca)는 상수이고, 빅오에서는 상수가 있을 경우 상수를 제거하니

∴ 로그가 상용로그(밑이 10)이던 자연로그(밑이 e, 오일러상수,2.718....)이던 2이던 중요x

=>그래서 밑을 무시하고 그냥 O(logn)으로 사용한다.

 

01-2-9 강의

1. 빅오에 대한 수학적 접근

*빅오의 수학적정의

두개의 함수f(n)과 g(n)이 주어졌을때, 모든 n≥k에 대하여 f(n)≤cg(n)을 만족하는 두개의 상수 c,k가 존재하면 f(n)의 빅오는 O(g(n))이다.

 

=>강의를 듣고 나의 해석

모든 n≥k에 대하여  -> 데이터량이 많을때

f(n)≤cg(n)을 만족하는

-> 빅오는 같은 데이터(k)일때 원래함수인 T(n)값보다 작다. 하지만 c배하면 T(n)값을 넘을수 있다.(같은패턴이니까)

 

ex) an²(=cg(n))과 n³(=f(n)) 비교

초반에는(=k값이 작을 때=데이터량이 적을 때) f(n)≤cg(n)를 만족할 수는 있으나, k값이 커지게 되면 만족할 수 없다.

->즉, n<k는 만족하나 n≥k는 만족불가

∴ c와 k의 조건이 둘다 만족해야 빅오가 될 수 있다.

∴ an²은 O(n²)이며, O(n³)이 될 수 없다.