Big O notation

@어려운 말은 차치하고

n이 클수록, 동작하는데 오래 걸리는 코드라 생각하자.

@이때, BigO는

N개의 아이템을 K(최악의 상황)번 탐색 했을 때의 lhs가 1이 된다는 것에서 K는 무엇이 되는가

= 최악의 상황일때, K는 어떻게 표현되는가.

@rule

생성된 시간복잡도 식에서 상수와 최고차항이 아닌 것은 제외한다.

@예시를 통한 이해

1. for문

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
	}

"최악의 경우"와 "최상의 경우"같은 것이 없는 상황이다.

 

언제든지 "최악의 경우" 또는 "최상의 경우"이다.

 

n개의 자료를 n번 탐색해야 하니.

 

N-K =1 -> K= (N-1)*(N-1)

 

O(N^2)

2. sequential search

"최악의 경우"에 n개의 자료를 전부 들여다보아야 1개의 값을 찾을 수 있다.

 

operation이 수행된다고 해서 자료가 줄어들진 않는다.

 

N-K = 1 -> K = N-1

 

O(N)

3. binary search

1번의 operation시, N은 N/2로 줄어든다.

2번의 operation시,N은 N/2 * 1/2 로 줄어든다.

K번의 operation시 N은 N/2 * (1/2)^K로 줄어든다.

 

따라서 양변에 로그를 씌우면 K = log2(N)이다.

 

O(log2(N))

 

 

###추가

 

1번시행 / N-1
2번시행 / N-2
K번시행 / N-K = 1  -> K = N-1

1번시행 /  (N/2)

2번시행 / (N/2)(1/2)
K번시행 / N * (1/2^K) = 1 -> K = log2(N)

 

###추가

 

위의 1번시행을 -> 1번만에 성공으로 바꿔서 읽어보라

 

O(n/2 + n/2^2 + ..). 이게 링크드리스트 바이너리서치인데 생각해볼것

 

링크드 리스트 바이너리 서치는 1번 시행 후에, 2번째 시행을 시행할때, 남은것들을 안봐도 된다는 뜻이 아니라서 그렇다. 해시와 다른점