[Powered by Google Translate] [섹션 3 - 더 편안한]
[롭 보덴 - 하버드 대학교 (Harvard University)]
>> [이 CS50입니다. - CS50.TV]
>> 그래서 첫 번째 질문은 이상하게 worded합니다.
GDB는 더 구체적으로 프로그램을 "디버깅"하지만 할 수 있습니다, 당신은 무슨 일을하게됩니까?
나는 거기에 대답을거야, 그리고 당신 정확히 예상 건지 모르겠어요
그래서 그것의 라인을 따라 그게 일이 있는거 같은데하면 단계적으로 할 수 있습니다
그와 상호 작용하는,이 프로그램을 통해 도보로, 변경 변수는이 모든 일을 -
기본적으로 완전히 프로그램의 실행을 제어
그리고 프로그램의 실행 특정 부분을 검사한다.
그래서 그 기능은 당신이 일을 디버깅 보자.
좋아요.
왜 이진 검색은 배열을 정렬 할 것을 요구합니까?
누가 그런 대답을 원하는가?
[학생]가 정렬되지 않은 경우 작동하지 않기 때문에. >> 그래. [웃음]
이 정렬되지 않을 경우, 다음의 절반에 분할 불가능
그리고 왼쪽으로 그 모든 걸 알고 점점 오른쪽으로 전부
중간 값보다 더 크다.
그럼 정렬해야합니다.
좋아요.
왜 제곱 n의 O에 거품 정렬은?
사람이 먼저 버블 정렬이 무슨 날인지 매우 빠른 높은 수준의 개요를 제공할까요?
[학생] 당신은 기본적으로 각 요소에 통과하고 처음 몇 요소를 확인합니다.
그들은 당신이 그들을 교체 곳에서라면, 당신은 다음 몇 요소 등을 확인합니다.
당신이 마지막에 도달하면 다음 가장 큰 요소가 끝 부분에 위치 알고,
그래서 당신은, 하나는 다음 겪고 계속 무시
각 시간은 당신이 더 변경 사항을 않을 때까지 적은 요소를 확인해야합니다. >> 그래.
당신이 그면에 배열 뒤집기를하는 경우 때문에 아래로 일어 서서 때문은, 버블 정렬 수직라고
다음 큰 값은 아래로 가라 앉을 것이며 작은 값은 위로 거품까지 것이다.
그게 그 이름을 방법입니다.
그리고 그래, 당신은 단지를 통해 이동합니다.
당신은 더 큰 가치를 교환, 배열 겪고 계속
아래로 가장 큰 값을 가져옵니다.
>> 왜 제곱 n의 O입니까?
첫째, 사람은 n의 제곱 O 왜하고 싶은 말은 무엇입니까?
[학생] 각 실행에 대해이 n 번에 가면 때문에.
당신은, 당신이 가장 큰 요소 끝까지 간 것 확신 할 수
다음은 많은 요소로 그 방법을 반복해야합니다. >> 그래.
그래서 큰 O가 의미하는과 큰 오메가 무슨 말인지 명심하십시오.
큰 O는 실제로 실행할 수있는 방법을 느린에 행 위처럼입니다.
따라서 제곱 n의 그것이 O를 말하여, 그것은 n의 O하지 않거나 다른 그 실행시킬 수 있습니다
선형 시간에하지만, N cubed의 O입니다
그것은 N cubed의 O에 묶여 때문입니다.
이 제곱 n의 O에 묶여있어 경우, 그것은 N cubed으로도 묶여있어.
따라서이 제곱 습니 있으며, 절대 최악의 경우는 제곱 N보다 더 할 수 없어
그 말은 제곱 N의 O 이유입니다.
그래, 그게 N 제곱으로 나오는 방법에 약간의 수학을 볼 수
우리는 목록에있는 다섯 가지를 가지고 있다면, 처음 몇 스왑 우리는 잠재적해야 할 수
이 이용을 위해? 의를 실제로하자 -
얼마나 많은 스왑 우리는 배열을 통해 버블 정렬의 첫 번째 실행에서해야하는거야?
[학생] N - 1. >> 그래.
>> 1-5 요소가있는 경우, 우리는 n을해야 할거야.
그런 다음 두 번째 하나를 얼마나 많은 스왑 우리가해야하는거야?
[학생] N - 2. >> 그래.
그리고 세 번째는 N이 될 것입니다 - 3, 그리고 편의를 위해 난 마지막 2 개의를 작성합니다
다음으로 우리는이 스왑 1 스왑을해야 할거야.
나는 마지막으로 하나 또는 실제로 일어난해야 할 수도 있고 그렇지 않을 수도 있습니다 같아요.
이 스왑입니까? 모르겠어요.
따라서 이것들은 총 스왑의 양이나해야 할 일이 적어도 비교합니다.
당신은 교환하지 않는 경우에도, 당신은 여전히​​ 값을 비교해야합니다.
따라서 N이 있습니다 - 배열을 통해 처음 실행 1 비교는.
당신이 이런 일을 정렬하는 경우, 일 똑바로 쌓아 그러니 실제로 6 일을하게
그럼 내가, 2, 1 3 다하겠습니다.
그러므로이 금액을 재 배열, 우리는 우리가 만들어 얼마나 많은 비교를보고 싶은
전체 알고리즘 인치
우리는 여기이 사람들을 가지고하면,
그런 다음에 우리가 아직도 있었다 그러나 많은 비교를 합산하고 있습니다.
그러나 우리는 이것들을 요약하고이를 합계하고이를 합계하면,
당신은 여전히​​ 같은 문제입니다. 우리는 그 특정 그룹을 합계.
>> 이제 우리는 3에게 N의를 합산하고 있습니다. 그것은 불과 3 N의 없습니다.
항상 N / 2 N의 질거야.
그래서 여기에 우리는 6가 발생합니다.
우리가 10 가지가 있으면, 우리는 사물의 5 개의 쌍에 대해이 그룹화 할 수
과 n + N + N + N + N이 생깁니다.
그럼 당신은 항상 N / 2 N의를 얻을 것 등이 우리는 N 제곱 / 2로를 조금합니다.
그리고 이제에 와서 일 반 요인,이지만
배열이 지남에 따라 각 반복을 통해 우리가 하나 더 비교는 사실 때문에
그래서 우리가이 극복하는 방법은 있지만, 아직도 제곱 습니됩니다.
우리는 반의 상수 요소에 대해 신경 쓰지 않습니다.
이와 같은 큰 O의 진짜 많이 수학 이러한 종류의 일을, 그냥에 의존 자,
산술 금액과 기하학적 시리즈 물건을하고,
하지만이 과정에서 대부분은 매우 간단합니다.
좋아요.
왜 삽입 정렬은 n의 오메가에? 오메가는 무엇을 의미합니까?
[한 번에 말하기 두 학생 - 이해할 수없는] >> 그래.
오메가 당신은 아래 행으로 생각 할 수 있습니다.
>> 따라서 삽입 정렬 알고리즘이 얼마나 효율적 상관없이,
에 관계없이에지나 목록, 항상 적어도 N 물건을 비교하는
아니면 N 일 동안 반복한다.
왜 그럴까요?
[학생] 때문에 목록이 이미 정렬되어있는 경우 다음을 통해 첫 번째 반복
만, 최초의 요소가 최소입니다 보장 할 수
두 번째 반복은 당신은 단지 첫 두가 보장 할 수
당신은 목록의 나머지는 정렬됩니다 알 수 없기 때문입니다. >> 그래.
당신은 최소한 완전히 정렬 된 목록에 통과하면 모든 요소를​​ 통해 가야
아무것도 주위에 이동 할 필요가 없다 볼 수 있습니다.
그래서 목록을 통해 전달 아, 그리고 이것은 이미 정렬 말은
당신이이 정렬하는지 알고에 각 요소를 확인하기 전에는 불가능
그들은 정렬 순서에 있는지 확인하십시오.
그래서 삽입 정렬에 행 낮은은 n의 오메가입니다.
최악의 경우는, 병합 정렬 시간 무엇을 실행중인
최악의 경우 다시 빅 O 것?
따라서 최악의 시나리오에 병합 정렬은 어떻게 실행합니까?
[학생] N 로그 N. >> 그래.
가장 빠른 일반적인 정렬 알고리즘은 N 로그 N 수 있습니다. 당신은 더 잘할 수 없습니다.
>> 이 특별한 경우가 있으며, 우리가 오늘 시간이 있으면 - 우리는 아마도 그게 좀 -
우리는 N 로그 N보다 나은 수행을 볼 수 있습니다.
그러나 일반적으로 경우에, 당신은 N 로그 N보다 더 할 수 없습니다.
그리고 병합 정렬은 N 로그 N이이 과정에 대해 알고 있어야 사람이되고 발생합니다.
그래서 우리는 실제로 오늘날 구현됩니다.
그리고 마지막으로, 더 이상 세 개의 문장에서 어떻게 선택 정렬 작업을합니까?
누군가에게 묻고 싶은 않으며, 당신의 문장을 계산합니다
왜냐하면 당신은 3 위에 가면 -
사람이 선택 정렬을 기억 하는가?
선택 정렬은 이름에서 기억 일반적으로 매우 간단합니다.
넌 그냥 배열을 통해 반복, 어쨌든 가장 큰 값이 아니면 작은 발견 -
당신이 들어 정렬간에 순서
그럼 우리가 작은에서 큰에 정리하고 있어요 가정 해 보겠습니다.
당신은 최소한의 요소가 무엇이든간에 찾고, 배열을 통해 반복
을 선택한 다음, 그냥 처음에 무엇이든을 바꾸고.
그리고 배열을 통해 두번째 패스에서 다시 최소 요소를 찾습니다
을 선택한 다음, 두 번째 위치에있는 것만을 바꾸고.
그래서 우리는 선별 및 최소 값을 선택하는
그리고 배열의 앞쪽으로 삽입하면이 정렬 될 때까지.
그 질문 있나?
>> 이러한 필연적으로 당신이 pset를 제출 할 때 작성해야하는 형태로 나타납니다.
사람들은 기본적으로 해당에 대한 답변입니다.
그럼 이제 문제를 코딩.
이미 이메일을 통해 발송 - 사람은 이메일을받지 못하셨습니까? 좋아요.
난 이미 이메일을 통해 우리가 사용하려고하고있는 공간을 발송
당신이 내 이름을 클릭하면 - 그리고 그래서 내가 바닥에 할 것 같아요
때문에 뒤로 R의 - 당신이 내 이름을 클릭하면 당신은이 버전을 볼 수 있습니다.
금요일 수정 1 전 이미 복사 공간에 코드를 붙여 넣을 수 것입니다
검색 문제에 대해 당신은 구현해야 할거야.
및 개정 2 우리가 그 후에 구현 정렬 일이 될 것입니다.
그럼 당신은 내 일 월요일 수정 1을 클릭하고 거기에서 작업 할 수 있습니다.
그리고 지금 우리는 이진 검색을 구현​​하고 싶습니다.
>> 사람은 의사 높은 수준의 설명을 제공하기 위해 하는가
무엇을 우리가 검색 할 필요가가는 건가요? 그래.
[학생] 당신은 배열의 중간을하고 원하는되는지 확인
보다 작거나 그 이상입니다.
그리고 더 있다면, 당신은 덜 반으로 이동
더 있다면, 당신은 더 반에 가서 당신은 반복 당신은 한 가지를 얻을 때까지.
[보덴] 그래.
우리의 숫자 배열이 이미 정렬이된다는 것을 명심,
그리고 그건 우리가 활용할 수 있으며, 우리가 먼저 확인 할 수 있다는 것을 의미
알았어, 내가 50 번째 찾고 있어요.
그래서 중간에 이동할 수 있습니다.
중동, 이건 일 짝수 때 정의하기 어렵다
하지만 우리가 항상 중간에 자르됩니다 거라고 만 말해 두지.
그래서 여기에 우리는 8 일이 있으므로, 중간은 16이 될 것입니다.
나는 50을 찾고 있는데, 50 대 16보다 큽니다.
그래서 지금은 기본적으로 이러한 요소로 내 배열을 처리 할 수​​ 있습니다.
난 16에서 온 모든 것을 던져 수 있습니다.
지금 내 배열은 이러한 4 가지 요소이고, 나는 반복한다.
그래서 내가 다시 중간을 찾고 싶어요, 어떤이 42가 될 것입니다.
42 50 이하이며, 그래서이 두 요소를 던져 수 있습니다.
이건 내 남은 배열입니다.
다시 중간을 찾을거야.
난 항상 왼쪽에 물건을 버린 건데 때문에, 50 나쁜 예를했던 것 같은데
하지만 같은 조치에 의해, 경우에 난 뭔가를 찾고 있어요
그리고 내가 현재보고 요소보다 덜
그런 다음 오른쪽에있는 모든 버릴거야.
이제 우리는 그렇게 구현해야합니다.
우리는 크기가 통과 할 필요가납니다.
우리는 또한 하드 코드 크기가 필요 없습니다.
우리가 제거한다면 # 정의 -
좋아요.
어떻게 멋지게 숫자 배열의 크기가 현재 무슨 알아낼 수 있나요?
>> 숫자 배열에서 얼마나 많은 요소?
[학생] 숫자, 괄호,. 길이?
[보덴]는 C.에 존재하지 않습니다
필요합니다. 길이입니다.
배열 속성을 필요가 없습니다, 배열의 더 길이 속성이 없습니다 때문에
그 그냥 갈거야 당신은 그러나 긴 줄 것이다.
[학생] 그것이 얼마나 많은 메모리를 확인하고 얼마나 많은에 의해 분할 - >> 그래.
그럼 어떻게 우리는이 얼마나 메모리를 볼 수 있나요? >> [학생] Sizeof. >> 네, sizeof.
Sizeof는 숫자 배열의 크기를 반환하는거야 연산자입니다.
그리고 그러나 많은 정수 할 거에요 시간은 정수의 크기 없습니다
그 실제로 차지 얼마나 기억 이니까.
나는 배열의 가지 수를 원하는하면,
그럼 내가 정수의 크기에 따라 나눌 싶은거야.
좋아요. 그래서 그런 날 여기서 크기 전달 할 수 있습니다.
이유는 전혀 크기로 전달해야하나요?
왜 그냥 int는 크기가 여기에 할 수 없어 = sizeof (건초 더미) / sizeof (int는)?
왜 작동하지 않는 이유는 무엇입니까?
[학생]은 전역 변수 아닙니다.
[보덴] 덤불이 존재 우리는 모래 사장으로 번호를 전달하고
그리고이 온 건지의 foreshadowing 종류입니다. 그래.
[학생] 건초 더미 그냥에 대한 참조이므로 해당 참조가 얼마나 큰 반환합니다.
그래.
난 당신이 정말 바로 아직 스택을 본 한 강의에서 의심?
우리는 그것에 대해 이야기를 나눴습니다.
귀하의 모든 변수는 저장하려고 곳 스택입니다.
>> 지역 변수에 할당에 대한 기억은 스택에 갈 수 있습니다
각 함수는 스택에 자신의 공간을지면 자신의 스택 프레임은이란이다.
그럼 메인은 스택 프레임을 가지고 있으며, 내부 그것의이 숫자 배열을 존재하는 것이다
그리고 크기 sizeof (숫자)이 될거야.
그것은 요소의 크기로 나눈 숫자의 크기를 갖게되는구나
하지만 메인의 스택 프레임 내의 모든 삶을 그.
우리가 검색을 호출하면 검색 자체 스택 프레임을 도착
자신의 공간을 지역 변수를 모두 저장할 수 있습니다.
그러나 이러한 주장은 - 그래서 모래 사장이 전체 배열의 복사본이 아닙니다.
우리는 검색에 사본으로 전체 배열에 전달하지 않습니다.
이건 그냥 배열에 대한 참조를 전달합니다.
따라서 검색이 참조를 통해이 숫자에 액세스 할 수 있습니다.
아직, 주의 스택 프레임의 내부에 살고있는 일들을 액세스있어
하지만 기본적으로, 우리는 포인터에 도착하면, 이는 곧 올 거예요,
이 포인터가 무엇인지입니다.
포인터는 일에 대한 참조이며, 당신은 물건을 액세스 할 포인터를 사용할 수 있습니다
다른 것들 '스택 프레임에서 해당합니다.
숫자가 메인에 로컬하더라도 그래서, 우리는 우리가 여전히이 포인터를 통해 액세스 할 수 있습니다.
그러나 단지 포인터이고, 단지 참조니까,
sizeof (건초 더미)는 단지 참조 자체의 크기를 반환합니다.
그것이 가리키는있어 물건의 크기를 반환하지 않습니다.
이 숫자의 실제 크기를 반환하지 않습니다.
우리가 원하는대로 그리고이 작동하지 않을 수 있습니다.
>> 그 질문 있나?
포인터는 오는 주에 훨씬 더 많은 유혈 자세히으로 없어 질 것입니다.
왜 표시되는 일, 대부분의 검색 물건 또는 정렬 많은, 그리고이 집은
거의 모든 배열의 실제 크기를해야 할거야
C에 속하기 때문이다, 우리는 배열의 크기가 뭔지는 전혀 감이 없습니다.
당신은 수동으로 들여 통과해야
방금 참조를 전달 있기 때문에 그리고 당신은 수동으로 전체 배열에 전달할 수 없습니다
그리고 참조의 크기를 얻을 수 없습니다.
좋아요.
이제 우리는 전에 설명 된 것을 구현하고 싶습니다.
당신은 잠시 동안 그 작업을 할 수 있습니다
그리고 당신은 모든 것을 완벽하게 백퍼센트 작업을 것에 대해 걱정할 필요가 없습니다.
당신이이 일을해야한다고 생각 방법에 대한 반 의사를 써주세요.
좋아요.
완전히 아직이 작업을 수행 할 필요가 없습니다.
그러나 사람은, 지금까지 일이있는 편안한 기분
뭔가처럼 우리가 함께 사용할 수 있습니까?
사람이 자원 봉사할까요? 아니면 내가 무작위로 선택됩니다.
그것은 바로 어떤 조치하지만 우리가 작업 상태로 수정할 수 있습니다 무언가가 될 필요가 없습니다.
[학생] 그래. 좋아요 >>.
그래서 작은 저장 아이콘을 클릭하여 수정 사항을 저장할 수 있습니다.
당신이 옳아, Ramya 거지? >> [학생] 그래. >> [보덴] 좋아요.
이제 당신의 버전을 볼 수 있으며, 모든 사용자가 수정을 끌어 수 있습니다.
그리고 여기에 우리가 있습니다 - 그래.
그럼 Ramya는 확실히 유효한 솔루션입니다 재귀 솔루션과 함께했다.
이 문제를 할 수있는 두 가지 방법이 있습니다.
당신도 반복적으로 또는 반복적으로 할 수 있습니다.
당신은 재귀 적으로 수행 할 수있는 발생하는 대부분의 문제는 반복적으로 수행 할 수 있습니다.
그래서 여기에 우리가 반복적으로 그것을 한 적이있어.
>> 누군가는 함수가 재귀 수 있도록 의미를 정의 할합니까?
[학생]는 당신이 기능이되면 자신을 호출
사실과 진실에 나오는 때까지 다음 자체를 호출합니다. >> 그래.
재귀 함수는 자신을 호출하는 기능입니다.
재귀 함수가 있어야 세 곳의 큰 가지가 있습니다.
먼저 분명히, 그 자체를 호출합니다.
두 번째는 기본 경우가 있습니다.
그런 점에서이 함수 자체를 호출 중지해야합니다
그의 기본 케이스는 무슨 일 것입니다.
그래서 여기 우리가 중지해야한다는 것을 알, 우리는 검색에 포기해야
시작은 끝을 동일 때 - 우리는 그게 뭘 뜻 갈거야.
그러나 마지막으로, 재귀 함수에 대한 중요 마지막으로 :
기능은 어떻게 든 기본 케이스를 접근해야합니다.
두 번째 재귀 호출을 할 때 실제로 아무것도 업데이트하지 않는 경우처럼,
당신은 말 그대로 그냥 같은 인수와 함께 다시 함수를 호출하는 경우
그리고 더 전역 변수는 변경하거나 아무 것도있다
당신은 기본 케이스에 도달하지 않습니다이 경우 좋지 인치
그것은 무한 재귀와 스택 오버플로 될 것입니다.
하지만 여기 우리는 우리가 시작 할 + 끝 / 2 업데이트 이후 업데이트가 일어나는 것을 볼
우리는 여기에서 시작 인수를 업데이트, 여기 최종 인수를 업데이트하고 있습니다.
이 모든 재귀 호출에서 우리가 뭔가를 업데이트하고 있습니다. 좋아요.
귀하의 솔루션을 통해 우리를 걸어 하시겠습니까? >> 물론이지.
나는 때마다 내가이 함수 호출을 너무 SearchHelp를 사용
나는 배열에 원하는 곳의 시작과 끝을 가지고
어디에서 나는 배열을 찾고 있어요.
>> 사고가 시작되는 중간 요소 + 끝 / 2인데 모든 단계에서,
우리가 찾고있는 같다?
그게 있다면, 우리는 그것을 발견, 나는 재귀의 수준을 통과하면 그 같아요.
그게 사실이 아니라면 그리고, 우리는, 배열의 중간 값이 너무 커서 있는지 확인
경우있는 우리는 시작부터 중간 색인으로 이동하여 배열의 왼쪽 이분의 일 봐.
그리고 그렇지 않으면 우리는 결국 반을.
[보덴] 좋아.
좋은 생각이에요.
좋아요, 몇 가지 있으므로, 실제로이 매우 높은 수준 일이
언니는이 과정에 대해 알아야 할하지 않습니다,하지만 사실입니다.
재귀 기능, 당신은 언제나 나쁜 것만은 면서요?
당신은 재귀 적으로 자신을 너무 많이 호출하는 경우, 당신은 스택 오버 플로우를하기 때문에
내가 전에 말했듯이 이후, 모든 기능은 자체 스택 프레임을 가져옵니다.
그래서 재귀 함수의 각 호출은 자신의 스택 프레임을 가져옵니다.
이 1,000 재귀 호출을한다면, 당신은 1000 스택 프레임을
빠르게 당신은 너무 많은 스택 프레임과 일들이 그냥 무단 필요로 이어집니다.
재귀 함수는 일반적으로 나쁜 그래서 그게.
그러나 재귀 함수의 좋은 일부는 꼬리 - 재귀 함수를이라고합니다
이는 컴파일러가이 통지하는 경우 하나의 예를 들어 할 일
하고해야, 내 생각 엔 - 꽝에 당신은 - O2의 깃발을 통과하면
다음이 꼬리 재귀이 발견하고 일 잘 할 것입니다.
>> 그것은 각 재귀 호출에 대해 다시 이상 같은 스택 프레임을 재사용합니다.
이 같은 스택 프레임을 사용하고 있기 때문에 그리고, 당신은 걱정하지 않아도됩니다
당신은 전에 말했듯이 이제까지 넘쳐을 쌓아, 같은 시간에,
당신은 TRUE를 반환 곳 한 번, 다음이 스택 프레임의 모든을 반환하는
그리고 SearchHelp은 9로 돌아가이의 열째 호출, 8로 돌아합니다.
그래서 그런 기능이 꼬리 재귀 때 일어날 필요가 없습니다.
그리고 어떤이 함수 꼬리 재귀 만드는 것은 통보는 그 searchHelp에 특정 통화에 대한
가 쌓아가 는걸 재귀 호출은 반환있어.
따라서 SearchHelp에 대한 첫 번째 호출에서, 우리는 하나 즉시 false를 반환
바로 TRUE를 반환, 또는 우리는 SearchHelp에 재귀 호출을
우리가 돌​​려하면 해당 호출이 반환 무엇입니다.
우리가 INT X = SearchHelp, 반품 X * 2와 같은 짓을한다면 우리는이 작업을 수행 할 수 없습니다
그냥 무작위로 변화.
>> 그래서 지금이 재귀 호출이 int는 X = SearchHelp 재귀 호출
실제로 반환해야 않기 때문에 꼬리가 더 이상은 재귀입니다
다시 이전 스택 프레임에 해당하므로 함수에 그 이전 호출
한 다음 반환 값으로 뭔가를 할 수 있습니다.
그래서이 꼬리 재귀가 아니라 꼬리 재귀 잘되기 전에 우리가했던 일. 그래.
[학생]하는 것은 두 번째 기본 케이스가 먼저 확인해야하지 않겠
당신이에게 인수를 전달 곳 때 상황이있을 수 있기 때문에
당신은 = 끝을 시작했지만, 그들은 바늘 값입니다.
끝이 바늘 값입니다 질문은 우리가이 사건을 실행할 수 없습니다되었습니다
또는 = 끝을 시작 적절 = 종료를 시작합니다
당신은 실제로, 아직 해당 특정 값을 확인하지 않은
그런 다음 + 끝 / 2를 시작은 같은 값 될 것입니다.
그러나 우리는 이미 true를 반환 한 우리는 실제로 값을 검사하지 않습니다.
크기가 0이면 따라서 최소한 첫 번째 전화에서, 우리는 False를 반환하고 싶습니다.
크기가 1이라면, 그 시작은 평등 끝으로 이동되지 않습니다
우리는 적어도 한 요소가 있는지 확인합니다.
하지만, 당신이 + 끝 / 2를 시작 위치를 우리가 경우에 결국 수 있다는 점에서 옳다고 생각
시작, 시작 + 끝 / 2와 같은 존재 종료
그러나 우리는 실제로 요소를 선택하지 마십시오.
>> 그래서 우리가 먼저 확인한다면 중간 요소는, 우리가 찾는 값
그러면 우리는 바로 TRUE를 반환 할 수 있습니다.
그들은 같은거야 다른 경우, 계속해서 아무런 변화가 없다
우리는 우리가 단일 요소 배열에있는 경우로 업데이트 할거야 때문입니다.
그 하나의 요소는 우리가 찾고있는 사람이없는 경우
모든게 잘못되었습니다. 그래.
[학생] 문제는, 크기부터 배열의 구성 요소 수보다 실제로 큰 것입니다
오프셋은 이미이 - >>은 따라서 크기가됩니다 -
[학생]는 배열의 크기가 0이라면 말 다음 SearchHelp는 실제로 0의 모래 사장을 검사합니다
첫 번째 통화.
>> 네 - 배열의 크기는 0을 가지고 0집니다.
그 일이 또 있지 - 좋은 수 있습니다. 의 생각 좀 해보자.
배열은 10 원소를 가지고 우리가 확인 가고있는 가운데 하나는 인덱스 5,이면
그래서 우리는 5를 확인하고, 값이 적은 말합시다.
그래서 우리는 5 이후에서 떨어져 모든 것을 던져 요.
그럼 끝 / 2의 새로운 끝 될 것입니다 + 시작
그래 그래서 항상 배열의 끝 넘어있을거야.
그건 마치하거나,​​ 이상한면이 사실이라면, 우리는, 말, 4를 확인 것
하지만 우리는 여전히 포기하겠다 니 -
그래 그래서 끝은 항상 배열의 실제 끝 이상 될 것입니다.
우리가에 초점을 맞추고있는 요소 그래서 끝은 항상 그 후에 하나가 될 것입니다.
시작 적 평등 말을한다면 그리고, 우리는 크기 0의 배열입니다.
>> 내가 생각했는데 다른 건 우리가 시작되는 시작을 업데이트하고 있습니다 + 끝 / 2입니다
그래서이 + 끝 / 2를 시작합니다 제가에 문제가있는 경우는,
우리가 확인하고있는 요소입니다.
자, 우리가이 10 요소 배열을 가지고 말한다. 뭐든간에.
그럼 끝 / 2이 같은 뭔가있을 것입니다 + 시작
그리고 그 값이 아니라면, 우리는 업데이트 할 말한다.
이 값은 더 크다, 그래서 우리는 배열의이 반쪽 좀보세요.
그래서 우리는 시작을 업데이트하는 방법, 우리는이 요소로 시작을 업데이트하고 있습니다.
그러나 아직도 작동 할 수 있습니다, 또는 적어도, 당신은 시작을 할 수 + 끝 / 2 + 1.
[학생] 당신은 + 끝을 시작 할 필요는 없습니다 [안 들리게] >> 그래.
우리는 이미이 요소를 확인하고 우리가 찾고있는 사람은 알아 있습니다.
그래서 우리는이 요소로 시작을 업데이트 할 필요가 없습니다.
우리는 그것을 생략하고이 요소하기 시작 업데이트 할 수 있습니다.
그리고 경우 적 있는데,이 끝이라고 말합시다,
이 것 때문에 시작을 누른 다음, + 끝을 시작 / 2이 될,
+ 끝을 시작 - 예, 나는 무한 재귀에 끝낼 수 있다고 생각합니다.
그냥 크기 2 크기 1 배열의 배열 보자 말한다. 이 일 것이라 생각합니다.
따라서 현재 시작 요소와 끝이없는 1이다.
그래서 우리가 확인하는 것하는 요소는,이 하나입니다
그리고 우리가 시작을 업데이트 할 때, 우리는 0 + 1 / 2,로 시작 업데이트
이는 시작이 요소가되는 우리를 다시 종료 예정이다.
>> 그래서 우리는 다시 이상 같은 요소를 확인하고 있습니다.
그래서이 모든 재귀 호출은 실제로 무언가를 업데이트해야하는 경우입니다.
그래서 우리는 사건이 시작 + 끝 / + 1 또는 다른 2 할 필요가
어디 우리가 실제로 시작을 업데이트하지.
누구나 다 봤어?
좋아요.
사람이이 솔루션이나 더 많은 댓글에 대해 질문이 있습니까?
좋아요. 사람이 우리가 볼 수있는 솔루션을 반복십니까?
우리 모두 재귀 적으로 그 짓을 한거야?
아니면 또 그 여자를 열 경우, 당신은 이전을 무시 아마 그랬을거야.
가 자동으로 저장합니까? 나는 긍정적 아니야.
사람이 반복십니까?
우리는 함께 통과하면 할 수 없습니다.
이 아이디어는 동일 될 것입니다.
솔루션을 반복.
우리는 기본적으로 같은 생각을하고 싶어요 할거야
우리는 배열의 새로운 끝을 추적하고 배열의 새로운 시작을 유지하려는
그리고 그게 반복 않습니다.
그리고 우리가 시작과 끝 어느 교차하면서 추적을 유지하고 있는지 경우,
그리고 우리는 그것을 찾을 수 없습니다 우리는 false를 반환 할 수 있습니다.
그럼 난해야하나요? 누구든지 꺼내 나에게 제안이나 코드가 있습니까?
[학생] 한동안 루프를 수행합니다. >> 그래.
당신은 루프를하고 싶은 것입니다.
>> 당신은 내가 끌어 수있는 코드가나요 무엇을 당신이 제안하는거야?
[학생] 그런 것 같아요. >> 좋아. 이 일이 쉬울 수 있습니다. 이름이 무엇입니까?
[학생] 루카스.
금요일 수정 1. 좋아요.
낮은 우리가 전에 시작이라는거야.
최대 우리가 이전에 종료라는 매우 일이 아닙니다.
사실, 끝은 배열 내에서 지금이다. 우리가 고려해야 할 요소입니다.
따라서 낮은이 0, 최대 배열의 크기 - 1
지금 우리는 반복하고 있으며, 우리는 확인하는 중입니다 -
난 당신이 통과 할 수 같아요.
이런 식으로 당신의 생각은 무엇입니까? 코드를 통해 저희를 걸어보세요.
[학생] 그래. 중간에있는 건초 더미 값을보고 바늘에 비교합니다.
오, 사실은, 그 뒤로해야 - 그게 당신의 바늘보다 더 있다면 그래서 당신은 원하는.
당신은 오른쪽 절반을 멀리 던져 싶을 거예요, 그래서 그래, 그 방법이 될 것입니다.
[보덴]는 그래서이 미만이어야 하는가? 그 말은 무엇입니까? >> [학생] 그래.
[보덴] 좋아. 조금 덜.
우리가보고있는 것은 우리가 원하는 것보다 작다면은,
그리고 그래, 우리는 왼쪽 절반을 버리려하고
어떤 우리가 생각하는 모든 업데이트하는 의미
배열의 오른쪽에 낮은 이동하여.
이 좋아 보인다.
내 말은, 우리가 이전에 말한 것과 같은 문제를 가지고 있다고 생각
어디에서 낮은은 0이며 최대 1이 낮은 다음입니다 + 위 / 2 다시 같은 일로 설정 할 경우.
>> 그리고 그런 경우가 아닌 경우에도, 그것은 적어도 아직 더 효율적입니다
단지 요소를 버릴 우리는 우리가 잘못 알고있는 바라 보았다.
따라서 낮은 + 위 / 2 + 1 - >> [학생] 그건 다른 방법이 있어야합니다.
[보덴] 또는이 있어야합니다 - 1, 다른 하나는 + 1 있어야합니다.
[학생] 그리고 더블이 있어야 등호. >> [보덴] 그래.
[학생] 그래.
좋아요.
그리고 마지막으로, 이제이 + 1이 있는지 - 1 일,
그게 - 그게되지 않을 수 있습니다 - 그것은 낮은에보다 큰 값을 끝내고 다시 수 있나요?
가능성이 있나요 - 난 무슨 일이 할 수있는 유일한 방법은 생각 하나? >> [학생] 내가 모르겠어요.
하지만립니다 도착 후 마이너스 도착하면 그 다음 1 - >> 그래.
[학생]은 가능성이 엉망 것입니다.
나는 단 한 잘해야한다고 생각
가 낮은 결국하는 사람들이 동일 할 것입니다, 나는 생각합니다.
사람들이 동일한 경우 그러나, 우리는 시작하는 동안 루프를 수행하지 않았을
그리고 우리가 값을 반환합니다. 그래서 지금 우리가 좋은 것 같아요.
공지 사항이이 문제를 더 이상 재귀 없다하더라도
우리가이 그렇게 쉽게 자체적으로 확인할 수있는 아이디어의 같은 종류가 적용
우리가 다시 이상 인덱스를 업데이트한다는 사실에 의해 재귀 솔루션,
우리는 문제가 작아하는거야, 우리는 배열의 하위 집합에 초점을하고 있습니다.
[학생] 낮은이 0과 최대 1이면, 그들은 모두, 0 + 1 / 2, 0으로가는거야 것
그리고 하나 + 1 것, 하나는 것 - 1.
[학생] 어디 ​​평등을 확인하는거야?
중간 사람이 실제로 바늘 경우처럼?
현재 그런 짓도하지 않았어? 오!
뭐냐면 경우 -
예. 시작하자 첫 번째 중간 말을하기 때문에 우리는 여기까지 테스트를하지 못하는 -
[학생] 실제로 바인딩을 버리지 똑같아.
당신이 바운드를 던져 버리면 그럼, 첫 번째 또는 무엇이든을 확인해야합니다.
아. 그래. >> [학생] 그래.
이제 우리는 우리가 현재를 바라 보았다 하나를 멀리 던진 것
그건 우리가 또한 현재이 필요합니다 의미합니다
(건초 더미은 [(낮은 + 최대) / 2] == 바늘), 우리는 TRUE를 반환 할 수 있습니다.
그리고 다른하거나하는 경우 넣어 있는지, 그건 말 그대로 같은 일을 의미합니다
이 사실이 반환했을 때문입니다.
그래서 다른 경우 올려 놓을 게요,하지만 중요하지 않습니다.
>> 그래서 다른이, 다른이,이 내가 할 일반적인 일이있는 경우
어디에 모든 여기 좋은 경우 경우에도
낮은가보다 클 수 없어 같은, 그 사실 여부에 대한 가치를 추론 없습니다.
낮은보다 작거나 같다면서 그래서 당신은뿐만 아니라 말할 수도
또는 낮은 미만 중에
저들은 같거나 낮은 경우 그래서, 통과 일
그리고 우리는이 루프의 탈출 할 수 있습니다.
질문, 문제, 의견이 있으십니까?
좋아요. 이 좋아 보인다.
이제 우리는 정렬을하고 싶어요.
우리가 저의 두 번째 버전으로 가면, 우리는 이와 같은 숫자를 볼 수
하지만 지금은 정렬 순서가 더 이상 없습니다.
그리고 우리는 N 로그 N의 O에서 알고리즘을 사용하여 정렬을 구현하고 싶습니다.
우리가 여기 구현해야하는 알고리즘을 것 같아? >> [학생] 병합 정렬.
[보덴] 그래. 병합 정렬은 수 있도록 우리가 할 수있는 일은 무엇이야, O (N 로그 N)입니다.
그리고 문제는 매우 유사한 될 것입니다
어디서 쉽게 재귀 솔루션을 자체적으로.
우리가 원하는 경우 또한, 반복적 인 솔루션을 가지고 올 수
하지만 재귀 여기 쉬워 질 것이며 우리는 재귀를해야합니다.
내 말은, 우리가 처음 병합 정렬 통과 될 듯
병합 정렬의 아름다운 동영상이 이미 있지만. [웃음]
그럼 저 밖에 정렬 병합 -이 문서의 많은 낭비하고 있습니다.
아, 왼쪽에 하나 남았어요.
따라서 병합합니다.
아, 1, 3, 5.
좋아요.
병합 두 개의 별도의 배열을 소요됩니다.
개별적으로 두 배열을 정렬됩니다 모두.
그래서 배열, 1, 3, 5, 정렬. 이 배열, 0, 2, 4, 정렬.
이제 어떻게 병합 어떻게해야하는 자체가 정렬됩니다 하나의 배열로 그들을 결합합니다.
그래서 우리는 그 내부에 이러한 요소를 갖게 돼 크기가 6 배열을 원하는
정렬 순서를 유지해야합니다.
>> 그래서 우리는 이러한 두 배열이 정렬되어 있다는 사실을 활용할 수
선형 시간에이 작업을 수행하려면,
선형 시간 의미이 배열은 크기 X이며,이 크기 Y 인 경우는,
다음 총 알고리즘은 O (X + Y)해야합니다. 좋아요.
제안 그럼.
[학생] 우리는 왼쪽에서 시작 될까요?
그럼 당신은 첫번째 다운 후 1 0을 놓을 게요 그리고 당신은 여기 2에있다.
그래서 당신이 오른쪽으로 움직 탭을 것 같은 그런거야. >> [보덴] 그래.
우리가 왼쪽 요소에 초점을 경우 다음 배열 둘 다하십시오.
두 배열이 정렬되기 때문에, 우리는 알이 두 요소
두 배열에서 가장 작은 요소입니다.
그래서 지난 2 요소의 1의 병합 배열에서 가장 작은 요소해야한다는 것을 의미합니다.
그건 아주 작은이 오른쪽이 시간에 한 것을 발생합니다.
0 미만이기 때문에 그래서 우리는, 0을 왼쪽에 삽입
그래서, 0을 첫 번째 위치에 삽입 후 우리는이 업데이트
이제 첫 번째 요소에 집중하기로하였습니다.
그리고 지금 우리는 반복한다.
이제 우리는 2 비교하고 1. 1 작, 그래서 우리는 1 삽입됩니다.
우리는이 사람을 가리 키도록이 포인터를 업데이트합니다.
이제 우리는 다시는 이런 짓을, 2 때문에. 이 업데이트,이 2, 3을 비교합니다.
다음이 업데이트 4, 5.
그럼 병합입니다.
>> 우리가 한 번만 각 요소를 통해 이동하고 있기 때문에 선형 시간입니다 분명해야합니다.
그래서 병합 정렬 이런 짓을하는 거지 구현에 가장 큰 단계입니다.
그리고 그리 어렵지도 않아.
걱정할 것 몇가지는 가자 우리가 1, 2, 3, 4, 5, 6을 병합 한 말입니다.
이 경우 우리는이 하나가 작아 질 것입니다 시나리오에 종료
그리고 우리가이 포인터를 업데이트이 하나가 작아 질 것입니다,이 업데이트
이 하나는 작은, 그리고 지금은 인식​​해야
당신이 실제로와 비교하는 요소가 부족했을 때.
우리는 이미이 전체 배열을 사용했기 때문에
이 배열의 모든 지금은 여기에 삽입됩니다.
우리는 언제나 우리의 배열 중 하나가 완전히 이미 병합되어있는 포인트로 실행한다면
다음에 우리가 다른 배열의 모든 요소를​​ 가지고 배열의 끝 부분에 삽입.
그래서 우리는 단지, 5, 6을 4 삽입 할 수 있습니다. 좋아요.
그 해보세요 한 것입니다.
그 1 단계해야 구현.
병합 그에 따라 다음 정렬, 그것은 2 단계, 2 단계 바보입니다.
우선은이 배열을 제공합니다.
따라서 정렬 병합 1 단계는 반복적으로 절반에 배열을 깰 것입니다.
그럼 절반에이 배열을 분할.
우리는 지금 4, 15, 16, 50 및 8, 23, 42, 108이 있습니다.
그리고 이제 다시는 이런 짓을 우리는 반쪽으로이 분할.
이면에 할 만합니다.
50, 4, 15, 16 그럼.
우리는 여기에 같은 일을 할 것입니다.
그리고 지금 우리는 다시 절반으로 나눠.
그리고 우리는 4, 15, 16, 50가 있습니다.
그래서 우리의 기본 케이스입니다.
배열의 크기가 1의지면, 우리는 절반으로 분할을 중지합니다.
>> 이제 우리는 이걸 어떻게하지?
이 또한 8, 23, 42, 그리고 108로 분석을 끝내고.
이제 우리는이 시점에서 건, 지금 병합 정렬의 두 방금 목록으로 쌍을 병합되어 단계.
그래서 우리는이를 병합하고 싶습니다. 우리는 병합 전화.
우리는 병합 정렬 순서이를 반환합니다 알아요.
4, 15.
이제 우리는 이러한 병합하려는 그건 정렬 순서들로 목록을 반환합니다
16, 50.
우리는 사람들을 병합 - 나는 쓸 수 - 8, 23, 42, 108.
그래서 우리는 한 번에 병합 쌍을 수 있습니다.
이제 우리는 다시 병합합니다.
그 자체로이 목록의 각이 정렬되고 있다는 사실을 알 수,
그리고 우리가 정렬됩니다 크기 4의 목록을 이러한 목록을 병합 할 수 있습니다
및 정렬 크기 4의 목록을 가져 두 목록을 병합합니다.
그리고 마지막으로, 우리는 정렬 크기 8 중 하나를 목록을 가져 오려면 크기 4의 두 목록을 병합 할 수 있습니다.
여기가 전체 N 로그 N 것을 확인하기 위해 우리는 이미 병합 선형 것을 보았다,
그래서 때 우리는 그렇게 병합의 전체 비용 같은 이들을 병합을 상대
이 두 목록에 단 2 때문입니다 -
또는 잘, 그것은 n의 O이지만, 여기에 N는이 두 요소이므로 2입니다.
그리고이 2 2되며이 2 2되며이 2 2 수
그래서 우리가해야하는 병합 전체에서, 우리는 n을하고 결국.
이처럼 + 2 + 2 + 2는 N이 8입니다
그래서이 세트에 통합의 비용 습니됩니다.
그리고 여기에 같은.
우리는이 2,이 두 병합되며 개별적으로이 병합은 수술을 4 이동합니다
이 병합,이 모든 사이에 다시 한번 수술을 4 차례 걸릴,하지만
우리가 합병을 N 총 일 결국, 그래서이 단계 N이 걸립니다.
그리고 각 단계는 통합 된 N 요소를 걸립니다.
>> 그리고 얼마나 많은 수준 있습니까?
각 수준에서의 배열은 크기를 2로 증가.
다음은 배열의 크기는 하나의 아르 여기가 사이즈 2의 야, 여기 사람들은, 크기 4 야
마지막으로, 그들은 크기가 8하고 있습니다.
이 배로 증가되어 있으므로 있기 때문에, 로그의 N이 수준의 총이있을거야하고 ​​있습니다.
따라서 로그 N 레벨, 각 레벨 복용 N 총 작업과,
우리는 N 로그 N 알고리즘을.
질문이 있으십니까?
사람들은 이미 구현하는 방법에 대한 진전이 좀 있었나요?
난 그냥 자신의 코드를 살펴볼 수 이미 상태에 아무도 없어요?
좀 기다려 줄 수 있습니다.
이 사람은 더 이상 될 것입니다.
나는 매우 재발하는 것이 좋습니다 -
당신은 병합에 대한 재귀을 할 필요가 없습니다
병합에 대한 재귀을 수행하기 때문에 당신은 다양한 크기의 무리를 통과 할거야.
당신은 할 수 있지만, 그것은 괴롭히는입니다.
그러나 정렬 자체에 대한 재귀 아주 간단합니다.
당신은 문자 그대로 오른쪽 절반에 정렬, 왼쪽 부분에 정렬를 호출합니다. 좋아요.
누구나 아직 당겨 수 있을까요?
아니면 좀 기다려주지.
좋아요.
누구든지 우리가 작업 할 수있어?
아니면 우리가 그냥이 작동하고 거기에서 확장됩니다.
>> 누구나 내가 살펴볼 수있는 이것보다 더 있나요?
[학생] 그래. 당신은 내를 당겨 수 있습니다. >> 좋아.
네!
[학생] 조건이 많이있었습니다. >> 오, 이런. 당신은 할 수 있습니다 -
[학생] 내가 저장해야합니다. >> 그래.
그래서 우리는 개별적으로 병합을 수행 했어요.
아,하지만 그렇게 나쁘지 않아.
좋아요.
그럼 정렬은 mergeSortHelp를 호출 자체입니다.
mergeSortHelp이 무엇을 우리에게 설명합니다.
[학생] MergeSortHelp 꽤 많이 두 가지 주요 단계를 수행,
이는 배열의 각 절반을 정렬하고 둘을 병합하는 것입니다.
[보덴] 그래, 그럼 잠깐만을 제공합니다.
내가이 생각을 - >> [학생] 내가 필요 -
그래. 난 뭔가를 누락되었습니다.
병합에서, 나는 새로운 배열을 만들 필요가 있다고 인식
나는 자리에 할 수 없어. >> 예. 당신은 할 수 있습니다. 수정.
[학생] 그래서 새로운 배열을 만들 수 있습니다.
나는 다시 변경하려면 병합의 끝 부분에 잊어 버렸습니다.
좋아요. 우리는 새로운 배열이 필요합니다.
병합 정렬에서는이 거의 항상 사실입니다.
더 나은 알고리즘 시간을 벌었의 비용의 일부
거의 항상 조금 더 많은 메모리를 사용하는 필요합니다.
그래서 여기, 당신이 아무리이 정렬 병합 없다
당신은 필연적으로 몇 가지 여분의 메모리를 사용해야합니다.
그 또는 그녀는 새로운 배열을 만들었습니다.
그리고는 말에 우리가 원래의 배열에 새로운 배열을 복사 할 필요가 말한다.
[학생] 내가 그래, 그렇게 생각 해요.
그 참조 또는 어떤에 의해 계산의 관점에서 작동 있을지 모르겠어 -
그래, 작동합니다. >> [학생] 좋아요.
이을 실행 해 봤어요? >> [학생] 아니, 아직. 좋아요 >>.
를 실행 해, 그리고 난 잠시 그​​것에 대해 얘기하자.
[학생] 난하지만 모든 함수 프로토 타입 모든이 필요합니다?
함수 프로토 타입. 예 - 오, 당신은 같은 의미합니다.
정렬 mergeSortHelp를 호출합니다.
>> 따라서 정렬 mergeSortHelp을 (를) 호출 할 수 있도록, mergeSortHelp이 두 정의되어 있어야합니다
정렬하기 전이나 우리는 프로토 타입을 필요 해요. 그냥 복사하는 붙여 넣습니다.
그리고 마찬가지로, mergeSortHelp는 병합 전화입니다
하지만 병합이 아직 정의되지 않은, 그래서 우리는 mergeSortHelp 알려 수
그게 병합 어떤 모양 것입니다, 그리고 그 걸.
mergeSortHelp 했어요.
우리가 더 기본 케이스가 없습니다있는 우리는 여기서 문제가 있습니다.
MergeSortHelp가 재귀이기 때문에, 모든 재귀 함수
재귀 자체를 호출 멈출 때를 알고 기본 케이스의 어떤 종류를해야 할 것입니다.
우리의 기본 사건은 여기서 무엇을 할 것입니까? 그래.
[학생] 크기가 1이면? >> [보덴] 예.
우리가 바로 본 자처럼, 우리는 분할 배열을 중지
일단 우리는 필연적으로 자신을 정렬 크기 1의 배열에 들어 갔어요.
크기가 1 동일 경우 그래서, 우리는 우리가, 배열이 이미 정렬됩니다 알고
그래서 우리는 그냥 돌아갈 수 있습니다.
>> 무효 야주의 때문에 특정 아무것도 반환하지 않습니다, 우리는 반환합니다.
좋아요. 그럼 그건 우리의 기본 케이스입니다.
나는 우리가, 크기 0의 배열을 병합 할 일이 경우, 기본 케이스도 할 수 있겠 군
우리는 아마 어떤 시점에서 중지하려면
그래서 우리는 단지 미만 2보다 작거나 1 같은 크기를 말할 수
이 지금 어떤 배열을 위해 일 할 수 있도록.
좋아요.
그럼 그건 우리의 기본 케이스입니다.
이제 병합을 통해 문의 걸어 나가고 싶어요?
이러한 모든 경우는 무엇을 의미합니까?
여기에, 우리는 같은 생각을하고있는 -
[학생] 내가 모든 mergeSortHelp 전화와 크기를 통과해야합니다.
나는 추가 기본으로 크기를 추가하고 크기 / 2처럼, 없습니다.
[보덴] 오, 크기 / 2, 크기 / 2. >> [학생] 그래, 또한뿐만 아니라 위의 기능 인치
[보덴] 여기? >> [학생] 바로 크기입니다. >> [보덴] 오. 크기, 크기? >> [학생] 그래.
[보덴] 좋아.
잠깐만 내 말 좀 들어 생각해 보자.
우리는 문제로 실행하려면 어떻게해야합니까?
우리는 항상 0으로 왼쪽을 치료하고 있습니다. >> [학생] 번호
너무 이상 해요. 미안 해요. 그것은 시작해야합니다. 그래.
[보덴] 좋아. 난 더 좋아.
그리고 끝. 좋아요.
그래서 지금은 병합을 통해 문의 걸어 나가고 싶어요? >> [학생] 좋아요.
난 내가 만든이 새로운 배열을 통해 걷고거야.
의 크기는 우리가 정렬 할 배열의 부분의 크기
내가 새로운 배열 단계에서 넣어해야하는 요소를 찾기 위해 노력.
배열의 왼쪽 이분의 일이 더 이상 요소가 계속되면 그게을 수행하는, 제가 처음으로 확인하고 있어요,
그렇지되면, 당신은 말에 의하면 다른 조건에 가서
좋아요, 오른쪽 배열에 있어야합니다, 우리는 newArray의 현재 색인에 넣어드립니다.
>> 배열의 오른쪽도 완료하는 경우 그리고 그렇지 않으면, 확인하고 있어요
이 경우 그냥 왼쪽에 넣어.
그래서 실제로 필요하지 않을 수도 있습니다. 잘 모르겠 는데요.
어쨌든, 두의 어느 다른 두 검사는 왼쪽이나 오른쪽 작은 수 있습니다.
또한 각각의 경우에, 나는 증가 중 자리 표시 자 증가거야.
[보덴] 좋아.
좋았어.
누구든지 의견이나 우려 사항이나 질문이 있습니까?
또는 다섯 것 같아 - - 우리가 존재에 물건을 가지고 있다고 사가지 경우 자
그러나 우리는, 왼쪽 배열은 우리가 병합 할 필요가 떨쳐 버리게되었는지 여부를 결정해야
오른쪽 배열은 우리가 병합 할 필요가 떨쳐 버리게되었는지 여부 -
나는 아무 것도 지적하고있는 겁니다.
따라서 왼쪽 배열 떨쳐 버리게 되었어 또는 오른쪽 배열 떨쳐 버리게되었는지 여부.
이러한 두 가지 경우입니다.
우리는 또한 왼쪽 것은 옳은 일 미만 여부의 사소한 경우 필요합니다.
그럼 우리가 왼쪽 일을 선택해주세요.
사람들은 경우입니다.
여기가했다, 그렇지 있다는 있도록.
배열을 떠났다. 이 1, 2, 3입니다. 좋아요. 응, 그것들은 우리가 어떻게 할 수도 네 가지입니다.
그리고 우리는이 솔루션을 반복적으로 이동하지 않습니다.
나는 권장하지 않습니다 -
병합 정렬은 재귀 모두 꼬리가 아닌 함수의 예입니다
어서, 어서 꼬리가 재귀 수 있도록 쉬운 일이 아니지
뿐만 아니라 그것이 반복하게하는 것은 매우 쉬운 일이 아닙니다.
이 매우 간단합니다.
병합 정렬의 구현
당신이 무슨 짓을하든를 병합하지, 당신은 병합을 구축거야.
>> 따라서 병합의 상단에 내장 정렬 재귀 적으로 단지이 세 행이다 병합합니다.
반복적으로, 그것은 생각이 더 짜증나는 더 어렵습니다.
하지만 mergeSortHelp부터 재귀 꼬리 아니라는 것을 - 그 자체가 전화했을 때 -
그것은 여전히​​이 재귀 호출 반환 후 일을해야합니다.
그래서 스택 프레임도이를 호출 한 후 계속 존재해야합니다.
그리고이 작업을 호출 할 때, 스택 프레임이 존재 계속해야합니다
심지어 전화 후, 우리는 여전히 병합 할 필요가 때문입니다.
그리고이 꼬리 재귀 수 있도록 nontrivial입니다.
질문이 있으십니까?
괜찮아요.
따라서 정렬 돌아 간다 - 아, 제가 보여 드리고 싶은 두 가지가 있습니다. 좋아요.
정렬로 돌아 간다, 우리는 신속하게이 작업을 수행합니다.
또는 검색 할 수 있습니다. 정렬? 정렬. 그래.
종류의 시작으로 돌아 간다.
우리는 어떤 알고리즘을 사용하여 해당 종류의 배열 알고리즘을 만들려면
n의 O 인치
그럼이 가능합니까? 누구든지 어떤 종류가 있습니까 -
언니가 전에 암시 -
우리는 N 로그 N에서 N의 O하도록 지속적으로에 대한 경우는,
우리는 우리의 알고리즘 시간 현명를 향상
이는 우리가를 만회하기 위해 수행해야 할 일가는거야? 의미
[학생] 공간. >> 그래. 우리는 더 많은 공간을 사용하려고하고 있습니다.
아니라 그저 더 많은 공간, 그것은 기하 급수적으로 더 많은 공간입니다.
그래서 알고리즘이 유형의 의사 무언가, 의사의 polynom 생각 -
유사 - 내가 기억 할 수 없습니다. 의사 무언가.
우리는 많은 공간을 사용할 필요하기 때문에 그건
이 달성하지만, 현실적인 아닌지 확인하십시오.
>> 그리고 어떻게 우리는이를 어떻게해야합니까?
우리가 보장 할 경우이를 달성 할 수있는 배열의 특정 요소
아래의 특정 크기입니다.
그래서, 단지 크기가 200입니다 가정하자
배열의 모든 요소는 다음과 크기가 200 개입니다.
그리고이 사실은 매우 현실적인입니다.
당신은 매우 쉽게 당신이 수있는 모든 것을 다 알고있는 배열을 할 수 있습니다
어떤 수보다 적은 될 것입니다.
당신이 절대적으로 거대한 벡터 또는 무언가가있는 경우 같은
하지만 모든 0과 5 사이가 될거야 알고
다음은이 일을 할 속도가 매우 빠르고거야.
그리고 요소에 관한 바운드는 5
이 바인딩 있도록 당신이 사용 거예요 얼마나 많은 메모리입니다.
따라서 바운드는 200 개입니다.
정수는 최대 4 억이 될 수 있기 때문에 이론적으로는 바인딩은 항상있다
하지만 그때 우리는 공간을 사용하려는 때문에 비현실적이야
4000000000의 순서 있습니다. 그래서 그게 비현실적이야.
하지만 여기 우리가 바운드 말하지는 200 개입니다.
n의 O에 일에 그 트릭은 우리가 크기의 기준은 준수라는 또 다른 배열을 것입니다.
그래서 사실,이에 대한 바로 가기입니다 - 꽝이 짓을한다면 잘 모르겠어요.
그러나 최소한 GCC에 - 난 가정 꽝도 그렇지 -
이 단지 0s로 전체 배열을 초기화합니다.
그 작업을 수행하지 않으려면 그럼, 제가 별도로 할 수있는 (INT I = 0;
내가 <BOUND, 나는 + +)와 카운트 [I] = 0;
이제 모든 것은 0으로 초기화됩니다.
나는 내 배열을 통해 반복
그리고 내가하고있는 건 각의 수를 계산하려고하는데 - 여기 가서하​​자.
우리는 4, 15, 16, 50, 8, 23, 42, 108이 있습니다.
내가 계산하는거야 요소 각각의 사건의 번호입니다.
의 실제로 어떤 반복과 여기에 몇 가지 더 추가 할 수 있습니다.
우리가 여기에있는 값이 그래서,의 값은 [I] 배열 될 것입니다.
그래서 발은 4 또는 8 또는 무엇이든 다 될 수 있습니다.
그리고 지금은 내가 본 적이 얼마나 많은 그 가치를 믿고있어
카운트 있도록 [발] + +;
이 작업을 수행 한 후 카운트는 0001과 같이 예정이다.
카운트를하자 [발] - + 1 준수.
>> 지금 우리가 0에서 시작하는 사실에 대해 설명 할 뿐이에요.
그래서, 만약 200, 가장 큰 숫자가 될거야
그리고 0-200은 201 일입니다.
우리가 한 4 때문에 중요 그래서, 00001처럼 보이게됩니다.
그럼 우리가 수의 8 색인에서 1을해야 0001이됩니다.
우리는 수의 23 색인에서 2해야합니다.
우리는 수의 42 색인에 2해야합니다.
그래서 우리는 수를 사용할 수 있습니다.
따라서 num_of_item = 카운트 [I].
그리고 num_of_item는 2 있다면, 우리는 수 세의 2를 삽입 할을 의미합니다
우리의 정렬 배열에.
그래서 우리는 우리가 배열로 얼마나 멀리를 추적해야합니다.
따라서 인덱스 = 0.
배열 - 그냥 쓰기됩니다.
개수 -
배열 [인덱스 + +] = 난;
내가 원하는거야? 그게 제가 원하는 것 같아요.
네, 좋은 보입니다. 좋아요.
그래서 모두가 내 카운트 배열의 목적은 무엇 알 겠죠?
이 숫자 각각의 사건의 수를 계산합니다.
그리고, 그 계산 배열을 통해 반복 있어요
그리고 카운트 배열의 i 번째 위치
내 정렬 배열에 나타납니다 나도 그게 횟수입니다.
4 건의 1이 될 것입니다 이유
8 건의 1이 될 것입니다, 23 건의는 2가 될 것입니다.
그래서 내 정렬 배열에 삽입하는 방법을 그들에게 많은입니다.
그럼 난 그냥 그렇게 해요.
내 정렬 배열에 빠져 num_of_item를 삽입하고 있습니다.
>> 질문이 있으십니까?
우리가 한번 이상 반복되어 있기 때문에 그리고 다시,이 선형 시간
하지만,이 번호로 어떻게 또한 선형입니다
그래서이 많이 귀하의 바인딩이 무엇인지에 따라 달라집니다.
200 바인딩으로, 그 그렇게 나쁘지 않아.
당신의 바운드 10,000 될거 경우, 그건 좀 더 나쁜
당신의 바운드가 4,000,000,000 될 것입니다 경우하지만 완전히 비현실적이야
이 배열은 비현실적인 is 크기 4000000000,의되어야 할 것이다.
그래서 그런 걸. 질문이 있으십니까?
[안 들리게 학생 응답] >> 좋아요.
우리가 겪고있을 때 나는 다른 일을 깨달았습니다.
나는 문제가 루카스의 아마도 우리가 본 모든 하나 하나의 생각.
나는 완전히 잊어 버렸습니다.
제가 댓글 싶어있는 유일한 방법은 당신이 인덱스 같은 것을 다루는 때
당신은 루프에 대해를 쓸 때 당신은 정말이 표시되지 않을
하지만 기술적으로, 때마다,이 인덱스를 다루고 있습니다
당신은 거의 항상 부호없는 (unsigned) 정수 처리해야합니다.
당신이 서명 정수 처리 할 때 그 이유는,
당신은이 서명 정수가 있고 당신이 그들을 함께 추가 있도록하는 경우
그리고 그 사람들도 큰를 종료 한 다음은 음수로 결국.
그래서 그런 정수 오버 플로우가 무엇입니다.
>> 난 2 억 10 억 추가하면, 나는 부정적인 1000000000이 생깁니다.
그 정수는 컴퓨터에서 작동 방법은 다음과 같습니다.
사용의 문제는 그래서 -
즉, 낮은은 2,000,000,000 일 경우를 제외하고 괜찮아, 최대 1,000,000,000 할 일
그리고이 1,000,000,000 음수가 될 것입니다, 그리고 나서 우리는 나눌 것이다 그 둘의
및 제외 500,000,000이 생깁니다.
그래서이 집이 당신이 배열을 통해 검색 할 일 경우에만 문제
일들이 있습니다.
낮은 +가 오버 플로우에게 무슨 일이 생긴다면, 그럼 그게 문제입니다.
즉시 우리가 그들을 서명하기로 한 후 2,000,000,000 1,000,000,000 플러스는 3 억.
2로 나누어 3000000000는 1.5 억.
그들은 서명되지 않은 너무 자마자, 모든 완벽한 곳입니다.
당신은 루프에 대해를 쓸 때 그리고 그렇게도 문제입니다
실제로, 아마 자동으로 수행합니다.
사실은 당신을 소리 것입니다.
이 숫자는 단지 정수에 너무 큰이지만, 경우에 따라서는 부호없는 정수에 적응
당신 지르지되며, 당신이 정말로 문제로 실행하지 못한 이유 인 것.
당신이 지수는 음수가 될 수 없다는 것을 볼 수 있습니다
그리고 당신은 배열을 통해 반복 할 때
당신은 거의 항상 INT 부호 말할 수 있지만, 당신은 정말 필요 없어요.
물건은 그냥뿐만 아니라 거의 작동 할 수 있습니다.
좋아요. [속삭임] 지금이 몇시입니까?
그냥 난 정말 빠르게 해줄 게 - 나는 보여주고 싶었다 마지막으로.
당신은 우리가 # 5 같은 걸로 MAX를 정의 할 수 있도록 우리가 # 정의했는지 알아?
MAX하지 보자. # 200 준수 정의합니다. 그건 우리가 전에했던 일이야.
그냥 복사 붙여 넣기를 할 것이다 상수를 정의 그
우리는 구속 작성하는 일마다.
>> 그래서 우리는 실제로 # 정의로 더 많은 작업을 수행 할 수 있습니다.
우리는 # 기능을 정의 할 수 있습니다.
그들은 정말 기능 아니지만 우리가 함수를 호출합니다.
예 MAX (X, Y) 같은 것하는 것은 (? : X X <Y Y)로 정의됩니다. 좋아요.
그럼 당신은 3 원 연산자 구문에 익숙해 져야만
하지만 x는 Y보다 작습니다? y를 돌아 다른 x를 반환합니다.
그래서,이 별도의 기능을 할 수 있습니다 볼 수 있습니다
BOOL MAX 2 인수를 같이하고 기능이 될 수이를 반환합니다.
이 같은 짓을 내가 볼 가장 일반적인 것들 중 하나입니다. 우리는 그들을 매크로 전화하십시오.
이 매크로입니다.
이 단지의 구문입​​니다.
당신이 원하는 건 뭐든지 할 수 매크로를 쓸 수 있습니다.
당신은 자주 printfs 물건을 디버깅 매크로를 참조하십시오.
printf의 일종 그래서, 밑줄 LINE을 강조처럼 C에 특별한 상수가 있습니다
2, LINE 밑줄 밑줄
내가 2 FUNC 밑줄 생각도 있습니다. 그게 수 있습니다. 그런 것 같아.
이러한 일들은 함수의 이름으로 대체됩니다
또는 중이 줄의 번호입니다.
자주, 당신은 여기 그때 그냥 쓸 수있는 디버깅 printfs를 작성
디버깅 그리고 줄 번호와 I가 할 일을 겪게 기능을 출력합니다
그렇게 DEBUG 문을 발생하는.
그리고 당신은 다른 일을 인쇄 할 수 있습니다.
따라서 해보세요해야 하나 내가 # DOUBLE_MAX을 정의하는 일 경우입니다
2 * y 및 2와 같은 무엇인가로 * X.
그럼 어떤 이유를 들어, 당신은 많은 것을 할 수있어.
따라서 매크로합니다.
이것은 실제로 고장 났어요.
나는 DOUBLE_MAX (3, 6)과 같은 짓을하여 전화를합니다.
그럼 무엇을 반환해야 하는가?
[학생] 12.
예, 12 반환해야 12이 반환됩니다.
3 x는 대체됩니다, 6 Y에 대한 대체, 우리는 12 2 * 6, 반환됩니다.
지금 이건 어때? 무엇을 반환해야 하는가?
[학생] 14. >> 이상적으로, 14.
문제는 작업을 정의하는 방법 해시는 문자 복사 및 붙여 넣기 일을 기억이다
거의 모든 걸, 그래서 어떤이로 해석 될 것입니다
1 + 6, 2 번 1 + 6, 2 회 3보다 3 이내의 거리에 있습니다.
>> 따라서 이런 이유로 당신은 거의 항상 괄호 안에 모든 것을 감싸.
당신은 거의 항상 괄호 안에 감싸 모든 변수.
내가 여기를 수행 할 필요가 없습니다되는 것처럼 당신은 필요 없어 경우도있다
미만이기 때문에 거의 언제나 일 것,
비록 그게 그 사실이 아닐 수도 있습니다.
DOUBLE_MAX (1 == 2)과 같은 터무니없는 일이있을 경우,
3 다음 미만으로 대체 당할 것이다 즉, 2 동일 동일
그리고 나서, 그 같은 2, 1보다 3 이하 할 않는거야
이는 우리가 원하는하지 않습니다.
따라서 모든 연산자 우선 순위 문제를 방지하기 위해,
항상 괄호 안에 넣어.
좋아요. 그리고 그은 5 시반 거예요.
당신이 pset에 대한 질문이 있으면 저희에게 알려주십시오.
재미있을 것, 그리고 해커 버전은 훨씬 더 현실적인입니다
작년의 해커 판보다, 그래서 우리는 당신의 많은 해보 바랍니다.
작년은 매우 압도적이었다.
>> [CS50.TV]