빅오(Big-O) 표기법

https://www.youtube.com/watch?v=6Iq5iMCVsXA&list=PLjSkJdbr_gFYSUYfnF_OGXtnGs2d3vWg7

위의 동영상을 보고 정리해보았습니다.

상수 시간 (Constant time) - O(1)

F(int[] n){
   return (n[0] == 0) ? true:false;
}

선형 시간 (Linear time) - O(n)

F(int[] n){
    for i=0 to n.length
    print i
}

이차 시간 (quadratic time) - O(n제곱)

F(int[] n){
	for i = 0 to n.length
		for j = 0 to n.length
			print i+j;
}

서브-이차 시간 (Sub-quadratic time) - O(nm)

F(int[] n, int[] m){
	for i = 0 to n.length
		for j = 0 to m.length
			print i + j;
}

다항 로그 시간 (Polylogarithmic time) / cubic time - O(n세제곱)

F(int[] n){
	for i = 0 to n.length
		for j = 0 to n.length
			for k = 0 to n.length
				print i + j + k;
}

지수 시간 (Exponential time) - O(2의 n승)

Fibonacci Numbers

F(n, r){
  if(n <= 0) return 0;
  else if (n == 1) return r[n] = 1;
  return r[n] = F(n - 1, r) + F(n - 2, r);
}

지수 시간 (Exponential time) - O(m의 n승)

로그 시간 (Logarithmic time) - O(log n)

binary search

F(k, arr, s, e){
	if(s > e) return -1;
	m = (s + e) / 2;
	if(arr[m] == k) return m;
	else if (arr[m] > k) return F(k, arr, s, m-1);
	else return F(k, arr, m+1, e);
}

O(Sqrt(n))

Square root?

Drop constants

O(2n) => O(n)