데이터구조와 알고리즘2回_이진검색

2回 이진검색 

#검색_探索

‡검색이란? 배열에서 특정 데이터를 찾는 것

-선형탐색 (linear search)

-이진탐색(binary search)

물론, 다른방법도 많다.

探索とは? 配列の中で特定のデータを探す 

– 線形探索（リニアサーチ）

 – 二分探索（バイナリサーチ） 

もちろん、見つからないこともある

‡선형검색_線形探索 

배열의 처음부터 하나씩 원하는 데이터와 일치여부를 조사함.

 配列の先頭からひとつずつ、目的のデータと一致するかどうかを調べていく

‡이진검색_二分探索

-선형검색보다 효율이 좋다.

- 배열의 값이 이미 오름차순이거나 내림차순이어야 된다.

-탐색범위를 절반으로 줄이면서 검색한다.

- 線形探索より効率が良い

 - ただし、配列の値がすでに昇順または降順に 並んでいないといけない 

- 探索範囲を半分に狭めつつ探す

‡이진검색 알고리즘_二分探索のアルゴリズム

데이터수를 N으로 한다.

검색범위는 전체범위에 초기화(가장왼쪽은 0 오른쪽은 N-1로 초기화)

다음과 같은 루프로 돈다.

-탐색범위에 값이 1개만 있을때: 적절한 값인지 조사하고 종료

-탐색범위의 중간위치에 있는 값을 얻는다

원하는값이 중간값과 동일시 -> 발견!

중간값보다 작을때 -> 오른쪽 끝값을 중간값-1로 설정

중간값보다 클때 -> 왼쪽끝값을 중간값+1로 설정

データ数を𝑁とする。 

 探索範囲は全範囲に初期化 (探索範囲の左端は0、右端は𝑁− 1に初期化) 

次のようなループを回す

– 探索範囲に値が一個だけ：目的の値かどうか調べて終了 

– 探索範囲の真ん中の位置にある値を取得 (真ん中の位置は（左端＋右端）÷２で分かる) 

1. 目的の値が真ん中の値に等しい＝見つかった！ 

2. 目的の値が真ん中の値より小さい -> 右端を真ん中のひとつ左に設定 

3. 目的の値が真ん中の値より大きい -> 左端を真ん中のひとつ右に設定

‡시간계산량_時間計算量

선형탐색 : 𝑂(𝑁) -처음부터 하나씩 비교하기 때문

이진검색 : 𝑂(log𝑁) - 𝑁이 증가해도 별로 일이 늘지 않는다.

왜 로그함수가 나올까?

線形探索 : 𝑂𝑂(𝑁𝑁) –先頭からひとつずつ比較をするため 

二分探索 : 𝑂𝑂(log𝑁𝑁) – 𝑁𝑁が増えてもあまり手間は増えない 

なぜ対数関数が出てくる？

‡이진검색의 시간계산량_二分探索の時間計算量

데이터수를 N으로 몇번 나누면 1이 될까?

그 횟수를 r이라고 하면 𝑁 = 2𝑟 

즉, 𝑟 = log2𝑁

각 단계에서의 계산량은 𝑂(1)

따라서, 전체에서는 𝑂(log𝑁)

データ数 𝑁を2で何回割ったら 1 になるか？ 

その回数を 𝑟 とすると、 𝑁 = 2𝑟 

つまり、𝑟 = log2𝑁

各段階での計算量は 𝑂(1) 

よって全体では 𝑂(log𝑁)

‡big-oh표기법으로 로그_オーダー記法での対数

 log₂𝑁와 log𝑁와 log10𝑁는 모두 𝑂(log𝑁) 이다.

로그밑이 얼마든지 상수배밖에 차이가 안나기 때문에

log2𝑁 = log10𝑁 × log₂10 

상수배는 big-oh표기법에서는 사라진다. -> 𝑂(log𝑁) 

 log₂𝑁とlog𝑁とlog10𝑁はいずれも𝑂(log𝑁) 

対数の底がいくらでも定数倍しか違わない l

log2𝑁 = log10𝑁 × log₂10 

定数倍の違いは オーダー記法だと 消える。

‡‡‡第2回課題‡‡‡

크기가 N인 int형 배열 a를 만들고 이 배열을 탐색한다.

N은 1000000, 10000000, 100000000 3가지를 시도한다.

값은 a[i] = i로 설정 (정렬된 데이터값을 가지기위해서)

크기가 M인 int형 배열 v를 만든다.

배열 v에 들어있는 값을 배열 a에서 탐색한다.

v안의 값들은 0에서 2N-1의 난수로 설정.(원하는 값을 찾을 수 없는 상황도 만들기위해)

배열 v에서 값을 하나씩 가지고 그 값을 배열 a에서 이진검색하고 시간을 측정한다.

M의 크기는 100000000 정도로 한다.

선형탐색으로도 만들어본다.

선형탐색은 시간이 오래걸리므로 M값을 100으로 한다.

N의 3가지값에 따라 두개의 탐색형식의 시간이 어떻게 바뀌는지 출력한다.

주의 : 실행시간은 clock()이라는 함수를 사용한다.(사용법은 인터넷에서 조사)

time()이라는 함수를 사용하지 않도록,

한번의 검색은 부정확함으로 많이 검색해서 값을 비교한다.

즉, M번 탐색해서 총시간을 M으로 나눈다.

binary.c

값이 binary값은 +값으로 증가해야되고

linear값은 x값으로 증가해야 정답이다.

처음에는 난 빠가사리기 때문에 저렇게 큰 값을 동적할당할 생각을 안했다.

저번시간에 그렇게 동적배열을 배웠건만... 그래서 세그먼트에러라는 오류만 계속 뜨면서 뻘짓하다가

세그먼트에러가 사용하고 있는 메모리가 겹치거나 할때 뜨는 오류라고 해서 고민하다가

동적할당을 했더니 됬다.ㅎㅎ 처음엔 내가 clock()함수를 잘못쓰고 있는건 줄 알고 얼마나 시간낭비를 했던지...

clock함수 쓰는법 

참고→http://naver.me/xUrgp9e8

그리고 어떻게 코드를 열심히 짰는데 마지막에 M번 반복한 결과 값을 내라고해서그거 생각한다고 또 시간 많이 썼다. 

N값도 3번 바꿔주면서 이진검색이랑 선형검색 둘다해야되고 또 이걸 전체적으로 M번 반복해야되서 머리가 복잡했다ㅠㅠ

안그래도 또 학생들 다 집에가고 혼자 실습실 쓰고 있어서 서러운데..순간 아무생각 안남...아니 하기싫었던 듯ㅋㅋㅋㅋ

내가 한게 효율적으로 맞는건진 잘 모르겠지만..여튼 했다! 뿌듯하다..ㅎ