>> 스피커 : 좋아,이 CS50이다.
이것은 주일의 단부이며, 만약 당신은 이미 이점을 촬영하지 않은
점심이있을 것을 알고 여기서 평소와 같이이 금요일
당신은 좋은 대화를 즐길 수 있습니다 불과 얼음의 음식
CS50의 일부와 직원과 친구들.
여기에이 URL로 향한다.
>> 지금 당신은 기억하거나, 수 곧 알게 될 수있다,
여기에 이​​런 것들을 어느 끝에서 밖으로 주어진다
많은 클래스의 학기.
소위 블루 시험 서적되는 당신은 시험의 답을 작성합니다.
지금은 여기가 26 예 각각 파란색 책,
Z까지 이름을 기록 그리고 실제로 이름은 단순하고 있다는 아르
Z를 통해 하나의 손 오늘의 목표
무엇을 계속 될 것입니다 우리가하지 않은, 월요일에 시작
너무 많은 코드를 찾는 게 아니라, 아이디어와 문제 해결을 찾고.
목표 중 하나와 이 과정의 약속
더 생각하도록 가르치는 것입니다 주의 깊게, 더 질서,
보다 효율적으로 문제를 해결한다.
그리고 실제로, 우리는 정말 그렇게 할 수 심지어 코드의 라인을 건드리지 않고.
그래서 코끼리의 몇 가지있다 여기까지 오늘, 오렌지와 블루,
우리가 하나의 자원 봉사를 얻을 수 있다면, 어쩌면 더 뒤로 평소보다에서.
어떻게 거기에 대해, 아래에 제공됩니다.
의 목표로 될 것입니다 도움이 플러스 여기에이 시험을 관리 할 수​​ 있습니다.
당신의 이름은 무엇입니까?
>> 청중 : 메리 베스.
스피커 : 메리 베스는 최대 어서.
내가 당신을 위해 여기에 마이크를하자.
만나서 반가워요.
>> 청중 : 만나서 반가워요.
스피커 : 좋아, 그래서 난이 여기에 푸른 책 Z를 통해,
나는 그 척거야 나는 학생 중 하나가
그들은 다소 무작위로오고있어 3 시간의 시험 블록의 끝에서,
그래서 그들은 일부에서 끝나는거야 같은 반 임의의 순서.
지금은 단지 순간에 당신의 작업은 것입니다 이 그들이 얼마나 실제로 나중에 ...하는
의 끝에서 턴 클래스 가능성이 높습니다.
당신의 임무는 이제 꽤 될 것입니다 단순히 우리를 위해이 파란색 책을 정렬하려면
부터 Z까지
>> 청중 : 아, 이것이다 영원히 걸릴 것.
>> 스피커 : 그리고 우리는 볼 것이다 당신이이 일을 할 때, 어떤 압력 없습니다.
청중 : 아니, 아니 압력 또는 아무것도.
>> 스피커 : 그리고 재미를 위해, 의는 타이머를 만들어 보자.
>> 관객 : 너무 재미, 너무 재미.
>> 스피커 : 나는 당신을 위해 마이크를 보유 할 수 있습니다.
좋아, 우리는 우리의 속도를 두 배로했습니다.
그 동안 그래서, 내가 무슨 포즈를 취하게 메리 베스에 대한 질문이 될 것
그녀가 무엇을하고있다, 방법은 그녀는이 문제를 해결하는 것에 대해가요?
그리고 사실, 당신은 없을 수도 있습니다 지금까지 뭔가에 대해 생각
당신이 선택할 때와 너무 간단 이 같은 26 책까지,
자연이 않는 그들에게 주문.
절차는 어떻게 것을 당신은 실제로 사용할 수 있습니까?
그것은 상당히 랜덤 단지 당신이 볼 첫 번째 따기
그 자리에 넣고?
먼저 주위에 당신의 손을 이동 마십시오 다음 B를 찾고 찾고?
당신은 살펴 마십시오 옆에 그 쪽 쌍
다만, 잠깐만,이 말을 오른쪽 아니며, 다음 순서를 바꿔?
우리는 월요일에 이미 보았다 다수의 방식이 있다는 것을
있는 우리는이 작업을 수행 할 수 있습니다 참으로 우리는 여기에서 끝 부분으로,
나는 아마 주 걸릴 것 무엇 메리 베스하고있다.
우리는 보인다 몇 더미가, 세 개의 작은 것 하나 더.
>> 청중 : 나는 그들을 주문 해요 나는이 편지를 발견 할 때
내가 아는 시퀀스에서 함께 것을, 그렇게하지 ​​않도록 나는 둘을 합친
유지에 대해 걱정할 필요가 책의 전체 행의 트랙.
그것은 처음입니다, 오, 그냥 여기이 스택을 가지고있다.
거의 같은 : SPEAKER 퍼즐 조각이
오른쪽 모양이 서로 일치.
청중 : 꽤 많이, 그래.
스피커 : OK, 훌륭한.
그리고 지금이 각각 더미는 아마도 정렬?
>> 청중 : 그래.
>> Z. 모든 통해 좋아, A : SPEAKER 오른쪽 축하합니다, 당신은 그것을했다.
당신은 선택할 수 있습니다.
블루?
좋아, 감사합니다.
그래서 메리 베스 제안 않았다 무엇을 그녀의 접근 방식은이었다,
하지만 또 다른 방법 것입니다 방법을 이런 일을 정렬에 대해 갈 수 있습니까?
당신이 뭘 할 수 있었 겠어요?
이길 기록했을 것이다 일분 50 정도의 초,
플러스 잊었 것들 계산합니다.
당신이 뭘 할 수 있었 겠어요?
그래?
청중 : 스택을 가져 가라.
처음부터 시작합니다.
서류를 확인합니다.
그리고 상위 하나 높으면 이상은, 어쩌면, 그들은 아르
아래는 하나의 높은, 다음을 전환합니다.
>> 스피커 : 좋아, 그럼 시작 상단과 하단에,
다음의 방식으로 작동합니다 안쪽으로 그런 그들을 스와핑?
비슷한 OK, 그래서 조금 거품 정렬, 정신,
하지만 극단적 인 선택 하지 인접 쌍.
그러나 그것의 짧은 거기에 있다는 것입니다 다양한 방법으로 확실하게 무리
우리는이 작업을 수행하고, 수 솔직히, 나는 가지를 생각
바로 몇 접근 방식을 채택?
당신은 네 개의 정렬 된 더미의 종류를했고, 다음 효과적으로 그들을 함께 병합.
그리고는 또 다른, daresay,이다 모두 기술.
당신은 하나의 큰 더미로 취급하지 않았다 당신은 네 개의 쿼드로 문제를 분할
당신이 의지하고 어떻게 든 경우 결국 그들을 병합.
>> 그럼 궁극적으로 살펴 보자, 우리는이 작업을 수행하는 방법을 다른.
우리는 개념을 공식화 거품 정렬 마지막 시간,
거품 정렬 리콜했다 우리가 가시화 알고리즘
여기까지 반 친구들의 팔과, 겉으로는 무작위로 처음 분류.
그리고 우리는 다음 경우 페어를 결정 이 요소는, 순서를 벗어난
간단하게 교환합니다.
그래서 네와 두 아르 분명히 순서가,
그래서 그 두 친구들 위치를 전환했다.
그리고 우리는 4-6 반복 다음 6 및 8, 각각의 반복에,
오른쪽으로 이동.
>> 그래서, 얼마나 많은 페어 8 명이 부여 에서 걷는 동안 비교 난 어땠냐
하나의 반복에서 왼쪽에서 오른쪽으로?
얼마나 많은 비교?
세븐, 오른쪽?
팔이 있다면 때문에 사람들은 그러나 당신은 한 쌍을
그들과 당신은 계속 이동 하나는, 우측 홉
당신은 팔을하지 않을거야 비교 비교할 수 없기 때문에
요소 자체에 대하여, 또는 것 그냥 무의미, 그래서 당신은 칠 수 있습니다.
또는보다 일반적으로, 만약 우리는 N 명을, 우리
n은 마이너스 1 비교를 할 거품 정렬과 함께.
>> 어떻게 좋은의 지금 생각해 보자 나 나쁜 거품 정렬 사실, 그리고 시도
우리 자신에게 어휘를 제공합니다 이 같은 비판 알고리즘에있는
곧 우리 자신의.
통한 첫 번째 패스 그래서 버블 정렬, 처음
나는에서 왼쪽에서 오른쪽으로 걸어 단, 나 N에서 1을 뺀 비교했다.
그리고이 될 것 내 측정 단위, 오른쪽?
나는 가지 이야기하고 산책하고, 다소 다소 느린, 빠른,
그래서 초 내 수를 계산 특히 말하고 있지 않습니다,
그러나 수를 카운트 내가 월요일에했던 작업,
이명을 비교, 그 느낌 측정의 좋은 장치 등을들 수있다.
>> 따라서 n은 마이너스 일 처음 단계, 하지만 무슨 일이 그 후 일이?
한 패스의 하나 상승 여력은 무엇입니까 달리 분류되지 않은 목록을?
당신은 요소에 대해 말해 무엇 저기 모든 방법은 누구인가?
그래?
그건 바로, 가장 큰 요소인가?
수 팔, 심지어 그녀는 비록 여기 시작마다 I
에 그녀를 비교 이웃, 그녀는 계속
오른쪽까지 버블 링 목록의 편.
그리고 사실, 그게 어디 있죠 알고리즘 이름을 가져옵니다.
>> 이제 논리에 의해 얼마나 많은 비교 나는 두 번째 시간에 확인해야
왼쪽에서 오른쪽으로 난 그 패스를 만들어?
n은 음이, 오른쪽?
난 경우 그냥 내 시간을 낭비 할 것 사람에 대해 팔을 비교 계속
다른 우리가 이미 알고 있기 때문에 그녀는 바로 이곳에 있었다.
그래서 조금이다 최적화, 다음 패스가 너무
플러스 N 마이너스 두 단계가 될 것입니다, 여기서 n은 사람의 수이다.
이제 가지도, 추정 수 당신은 컴퓨터 과학자하지 않으면,
방법이 끝납니다.
이 알고리즘의 끝에서, 아마도 당신은 단지 하나의 비교 왼쪽 있어요.
당신은 가지를 해결해야 이 경우에 목록의 시작
하나는 순서를 벗어난 그리고 하나, 둘이어야한다
그래서 이것은 밖으로 바닥에 닿을 플러스 일 최종 비교.
>> 이제 점, 점, 파도의 점 종류가 있어요 수분이 몇 가지 세부 사항에서 손,
하지만 그냥 가서 간단하게 할 수 있습니다.
당신은 높은에서 호출하는 경우 당신의 학교, 솔직히 많이
했습니다 수학 책 약간의 컨닝 페이퍼
전면 커버 나에 을 보여 주었다 뒷 표지
무엇처럼 시리즈 합산 이것은 궁극적으로까지 추가했다.
일반적인 경우에, 당신은이 있다면 N 등의 변수, 그리고 실제로이 하나,
당신이 바라 보았다 경우 오래된 학교 수학 책,
당신이 실제로 볼 것 여기에이 금액까지 추가
n 번 N에서 1을 뺀 모든 2로 나눈.
이제 나를 그냥 규정하자 이 때문에 믿음의 도약에 해당하는
즉,이 요약 무엇 까지, 우리는 할 수
보다 일반적인 경우에 그것을 증명한다.
하지만 지금의이을 확장 할 수 있습니다.
그래서이를 곱하자, 그래서 그건 N 제곱 마이너스 N, 모두 2로 나눈.
즉, 정말 N 제곱입니다 마이너스 n은 2 이상, 2로 나눈
그래서 모든 친절하고 흥미로운.
하지만 우리 경우 어떻게 지금 플러그 - 인 가치인가?
나는 팔이 없었한다고 가정 사람들은, 그러나 백만을 말한다.
그리고 백만 때문 만 그것은 꽤 큰 숫자이다
의는 점에서 연결하고 어떻게되는지 보자.
나는 그 공식에 만 연결하면 그래서 나는 백만 제곱 줄게
2로 나눈 값을 뺀 백만, 2로 나눈.
지금 무슨 일이 있음은 동일하게거야?
그래서 500,000,000,000, 마이너스 50.
그리고 나는 실제로 할 경우 그 수학 밖으로, 그 수단
그 백만 정렬 버블 정렬을 가진 사람
나에게 499,999,500,000 걸릴 수 있습니다 결국 단계 또는 비교,
우리는 단지 추정하는 것입니다.
>> 즉, 아주 느린 느낌이 있지만, 솔직히 하나의 특정 입력을 측정
이처럼 모든 것을 이야기하지 않습니다.
그러나 실제로는 N 등이 제안 않습니다 크고 큰,이 알고리즘을 가져옵니다
가지 느낌이 더와 더 나쁜, 또는 당신이 정말로
그 고통을 느끼기 시작 지수, 즉, n은 제곱
이는 꽤 빨리 추가합니다.
그리고이 내용은 아니다 사실, 사람들에 손실
몇 년 전 어느 상원 의원 누구 운동, 인터뷰를 위해 앉아
구글의 에릭 슈미트, 당시 CEO,
하고 질문에 도전했다 많은 오늘날 우리가 탐구하고있다.
이제 살펴 보자.
>> [동영상 재생]
>> 상원 의원님, 당신은 여기 구글, 그리고 내가 좋아하는
대통령의 생각하는 면접 등.
지금은 구하기 힘든 거지? 대통령으로 작업,
당신은 지금 혹독한 통해 것입니다.
그것은 구글에 취업을하는 것도 어렵다.
우리는 질문이, 우리 우리의 후보의 질문을,
이 한 래리 Schwimmer에서입니다.
뭐 ... 너희들은 내가 생각 해요 농담이 바로 여기입니다.
가장 효율적인 방법으로는 무엇입니까 만 32 비트 정수를 정렬?
>> 그게 ...
>> 미안 해요, 만약 ...
>> - 아니, 아니, 아니.
나는 거품 정렬을 생각 갈 수있는 잘못된 방법이 될 것입니다.
>> 제발, 누가 그에게 이런 말 했어요?
나는 컴퓨터를 보지 않았다 당신의 배경에서 과학입니다.
>> 귀신 잡는 거기에 우리의 스파이를 얻었다.
>> - 좋아,하자 다른 물어 보자 면접 질문입니다.
>> [END VIDEO 재생]
>> 스피커 : 그래서 이야기 하지만 특정 숫자,
모두 도움이 될 수 없습니다.
그것은 삶의 교훈 버블 아니다 정렬 만 입력을 제공,
많은 500,000,000,000 등의 조치를 취할 수 있습니다.
당신은 정말 일반화 할 수 없습니다 너무 효과적으로 것과
좋은 디자인 결정을 내릴 프로그램을 작성할 때.
그럼 방법에 불구하고 집중하자 우리는이 결과를 단순화 할 수 있습니다.
>> 그래서 여기에 노란색으로 강조했습니다 N의 결과는 2의 제곱으로 나눈
그렇게 만 제곱 2로 나눈 다음
내가 강조했는지 궁극적 인 대답했다
우리가 떨어져 차감 후 N 2로 나눈.
그리고 지금 만들려고 해요 주장이며, 오프 빼면 누가 도대체​​ 무슨 상관이야
이 조금 넘는 오래된 N 때 첫번째 이 공식의 일부가 너무 크다?
그것은 다른 사람을 지배한다 이 용어는, n은 2로 나눈 제곱
로, 명확하게, 훨씬 더 큰 N은 백만처럼 커진다
그건 정말에서 큰 차이가 있습니다 500000000000 사이에 하루의 끝
및 499,999,500,000?
정말.
그리고 지금 우리가 갈거야 컴퓨터 과학자가 같이
그 낮은 차항을 무시하고 이 정말 같은 것을 가지고
다만로 단순화 중요거야 용어입니다.
더 큰 우리의 데이터 세트는 더 커 우리의 데이터베이스는, 더 많은 웹 페이지를 얻을
우리는 더 많은 검색해야 친구가 페이스 북에있다.
>> n이 커질수록, 우리가 정말이야 가장 큰 관심 예정
의 이러한 분석 용어 우리의 알고리즘 성능을 제공합니다.
그리고 당신이 무엇을 알고, 말할거야, 버블 정렬은 큰 O의 순서에,
N의 주문에 제곱.
그것은 정확히 n은 아니다 우리가 본 것처럼 제곱,
하지만 누가 정말 걱정 그 작은 용어에 대한,
솔직히 누가 정말 우리가 2로 나눈다면 상관이야?
그건 그냥 상수 요소입니다.
그리고 250 대 500,000,000,000입니다 억 거래의 정말 큰?
난 그냥 일년 기다릴 수, 말 그대로 내 노트북​​을하자
하드웨어에서 두 배 빠르게 얻을 와 차이의 종류
단지 시간이 지남에 따라 자연적으로 사라집니다.
>> 우리가 걱정하는 것은 식, 부분
다를 것 식의 우리의 입력이 커지고수록.
그리고 사실, 현실 세계에서, 즉, 점점 일어나고있는 일이지
우리의 문제에 대한 입력과 알고리즘은 더 커지고있다.
그래서 큰 O가 표기 될 것입니다, 점근 표기법, 우리가 단지
컴퓨터 과학자가 설명하기로 사용 성능 또는 실행 시간
알고리즘의.
우리는 알고리즘을 비교할 수 있도록 서면 다른 컴퓨터에
다른 사람들에 의해 사용함으로써 일부 근본적으로 유사한 메트릭
비교의 수처럼 당신이있어 어쩌면 스왑의 수를 결정하거나,
당신은하고 있어요.
>> 우리가하지 않을거야 카운트 시간이며
그 시계에 전달 일반적으로 벽에.
우리가 걱정하지 않을거야 에 대해 얼마나 많은 메모리입니다
당신은 오늘을 사용하는 즉 비록, 이상
우리가 측정 할 수있는 다른 자원.
우리는 우리의 분석의 기준으로 볼거야 그냥 기본 작업에, 사람,
솔직히, 당신은 시각적으로 볼 수 있습니다.
N의 큰 O와 같은 뭔가 그래서 제곱, 나는 N의 O 제곱 주장
위 소위에 바인딩 버블 정렬의 실행 시간.
즉, 당신이 경우 가 있음을 주장하고 싶어
얼마나 많은에이 상한 알고리즘이 걸릴 수 있습니다 단계,
그것은 N의 큰 O에있을 것 이 경우 제곱, 상한.
>> 내가 대신을 변경하는 경우 이야기는하지 버블 정렬에 대해 할 수
그러나이 상한에 대한 정보가 포함되어 있습니다.
당신은 알고리즘을 생각할 수 우리는 이미 검토 한 것을
그 상한, 최대 시간이나 작업의 측정,
경계라고 할 것이다 N에 의하여, 선형 함수,
하지 곡선이다 차 한?
알고리즘이 그 남자들 항상 더 이상 수행되지 않습니다
N 단계, 또는 같은보다 2N 단계 또는 3N 단계?
그래?
>> 청중 : 찾기 목록에서 가장 큰 수?
>> 스피커 : 완벽한 찾는 목록에서 가장 큰 수입니다.
나는 목록을 제공하고있어 경우 예를 들어 사람,
사람들 각각은 숫자를 잡고 최대 수는 무엇인가
단계는 저를 취해야한다, 합리적으로 스마트 사람,
이 목록에서 가장 큰 사람을 찾는 방법은?
N, 오른쪽?
최악의 경우, 여기서 인해 가장 큰 값이 될 수 있을까요?
오른쪽 끝에있는 모든 방법.
최악의 경우에 따라서 상단 구속, 나는 수도
모든 길을 가야 여기와처럼,
아, 여기 여덟이다, 또는 값이 무엇이든.
지금은 그냥 바보 같은 것 나는 오른쪽으로 갈 유지하는 경우?
점점 더 많은 요소를 찾고 그 중 마지막이 넘으면?
그래서 확실하게, n은 상한이다.
나는 취할 필요가 없습니다 보다 더 많은 단계.
>> 그래서 그 대신하면 내가 제안 무엇을 이 세상에서 알고리즘이있다 그
야 실행 시간이 로그 n의 큰 O에 묶여, n은 로그인?
우리는 어디에서 이것을 전에 본 적 있어요?
그래?
>> 청중 : 전화 번호부에 문제점을?
스피커 : 전화 번호부 문제처럼.
방법의 측정 무엇 많은 시간 또는 얼마나 많은 눈물을
나 같은 사람을 찾기 위해 걸렸다 전화 번호부에서 마이크 스미스?
우리는 로그 N을 요구했다, 그리고 심지어 익숙하지 않은 경우 또는 그것입니다
무엇을 조금 헷갈리는 로그 또는 지수이었다,
그냥 로그 N 기억 일반적으로 프로세스를 지칭
이 경우, 분할 다시, 다시 반으로 뭔가
다시, 다시, 등이 그 당신이 그렇게하는 것처럼 점점 더 작은 가져옵니다.
>> n은 물론, 의미의 그래서 로그 전화 번호부 예,
이론 이진 검색에, 때 칠판에 가상 문을했다
또는 숀 때 무언가를 찾고.
그는 이진 검색을 사용했다면, N 로그 얼마에 상한 것
걸리는 시간.
그러나에서 실행하는 알고리즘 n은 어떤 키 세부 사항을 가정셨습니까?
목록이 오른쪽으로 정렬되었는지?
당신의 알고리즘은 경우 잘못 입력은 정렬되지 않습니다
아직 당신이 사용하는 이진 검색과 같은
당신이 이동할 수 있기 때문에 바로 요소를 통해
실현하지 않고는 참으로있다.
>> 지금 이것은 하나의 큰 O를 무엇을 의미하는 것인가?
이 알고리즘 것을 의미하지 않는다 , 오직 하나의 단계 소요
그냥이 소요 의미 단계의 상수.
어쩌면 그것은 아마도 그건, 1이다 10, 어쩌면 1000입니다,
그러나 독립적 야 문제의 크기.
아무리 큰 n은, 일정 시간 알고리즘
항상 동일한 단계 번호 걸린다.
그렇다면 알고리즘 수 있습니다 우리는에 대해 아니면 그냥 얘기했습니다
직관적으로 그 것을 당신에게 온다 항상 소위 일정 시간에 실행?
그래?
>> 관객 : 두 숫자를 추가합니다.
스피커는 : 두 숫자를 추가 2 더하기 2는 완료, 4에 해당합니다.
그래서 작동 할 수 있습니다, 그 밖의 무엇?
어떻게 더 현실 세계에 대한, 그래?
>> 청중 : 찾기 목록에 제일 먼저.
SPEAKER : 제 찾기 목록에있는 요소 확인합니다.
우리는 실제로 얘기했습니다 이미 배열에 대한,
에서 당신 얻는 방법 배열의 첫 번째 요소
아무리 긴 배열은 C 코드에?
당신은 브래킷처럼 사용 제로 표기는, 빵, 거기있어.
그리고 옆으로 참으로 배열, 지원 뭔가 일반적으로 공지
랜덤 액세스와 같은, 랜덤 액세스 메모리, 말 그대로 수 있기 때문에
어느 한 장소로 이동합니다.
우리는 단순히이 더 많은 작업을 수행 할 수 있습니다 우리는 주 제로로 되감기 할 수 있습니다
때 우리는 스크래치를했다.
그것은 걸릴 않았다 얼마나 많은 시간을 스크래치에서 블록이 실행하는 말?
그냥 일정 시간, 오른쪽?
, 뭔가 말 말 뭔가, 그것은 중요하지 않습니다
큰 상처 세계가 얼마나, 그것은 항상 동일한 시간이 걸릴 것
단순히 무언가를 말할 수 있습니다.
>> 그래서 일정 시간이있어, 하지만 플립 측면은 무엇인가?
그 상위 인 경우 경계, 우리는 무엇을하려는 경우
하한을 설명하기 위해 우리의 알고리즘의 실행 시간을?
거의 최상의 경우 잠재적으로, 만약에 당신,
이 용어는 최선을 적용 할 수 있지만 의 경우, 최악의 경우, 평균의 경우 더
일반적으로,하지만 그냥 집중하자 하한에 더 일반적으로.
무슨 일이있는 알고리즘이다 하부는, N 단계의 경계
또는 2N 단계 또는 3N 단계?
n 개의 단계 중 일부 인자 즉, 그 하한입니다.
그래?
>> 대상 : 거품 정렬?
>> 스피커는 : 버블 정렬이됩니다 당신이 최소한 n 개의 단계, 왜?
그 이유는 무엇입니까?
왜 그 시작은 당신에게 와서해야 직관적으로,이 경우에도 단지
아직?
그래?
>> 청중 : [들리지].
스피커 : 그렇지.
의 최상의 시나리오 거품 정렬 알고리즘을 많이
나는 당신에게 8 명이 손 경우 누가 이미 분류되어,
그것은 어리석은 것 당신을 위해, 알고리즘,
앞뒤로 이동합니다 두 번 이상, 오른쪽?
즉시로 인해 한 번 목록을 도보
당신이 실현 오해야, 내가 만든 없음 스왑이 목록은 종료 정렬됩니다.
그러나 그것은 당신이 N 조치를 취할 것입니다.
>> 그리고 반대로, 어떻게 다른거야 그것에 대해 생각의 방법은?
버블 정렬은 오메가입니다, 그래서 N의, 말하자면,
당신이 보면 때문에 n보다 적은 요소, 무엇을
근본적인 문제는 무엇입니까?
이 분류 있다면 당신이 바로 모른다.
우리는 팔에 힘 눈을 인간 사람과는 같이 오, 정렬 할 수있어
그 날 N 단계를 수행하지 못했지만, 그것은했다.
당신의 눈에도 종류의 생각 의 비전의 큰 필드가
당신은 팔 요소 보았다, 당신은 팔명 보았다
그 효과적으로 여덟 단계를합니다.
그리고 나는 전체를 통해 도보 경우에만 목록 내가 예, 분류, 실현 않습니다.
나는 중지하면 중간의 모든 생각 오른쪽이 꽤 지금까지 분류되어있어,
이 분류 아니에요 확률은 무엇입니까?
즉, 정확하지 않을 알고리즘.
더 빨리,하지만 잘못 될 수 있습니다.
>> 그래서 지금 우리는 방법을 하한을 기술
일정한 시간에 대한 무엇?
무엇 낮은이있는 알고리즘이다 하나는 실행 시간에 구속?
1 단계, 2 단계, 10 단계, 그러나 상수 N 독립적
입력의 크기?
그래, 다시.
>> 청중 : PRINTF?
스피커 : 무엇입니까?
청중 : PRINTF?
스피커 : PRINTF.
확인, 확인을 클릭합니다.
그래서 단계의 고정 번호를합니다.
그리고 지금은 그 아니예요한다 우리는 C 코드에 대해 얘기하고
하지 스크래치, 뭔가 말처럼, printf와 함께,
우리는 조심 얻을 시작해야합니다.
printf의 걸릴 않기 때문에 입력은 문자열입니다,
문자열은 기술적으로 길이가 않습니다.
우리가 지금 선택 싶다면 당신, 당신이 괜찮다면,
기술적으로 우리는 printf의를 주장 할 수 가변 길이의 입력을 받아 않습니다,
확실히 그것은 이상이 소요될 수 있습니다 시간이 긴 문자열을 인쇄합니다
이 길이보다.
>> 그래서 우리는 무엇을 고려하는 경우 정렬 및 예제를 찾고?
휴대 전화의 마이크 스미스는 요 책, 또는 더 일반적으로 이진 검색?
최선의 경우, 어떤 일이 일어날 수 있습니까?
I는, BAM, 전화 번호부를 열고 마이크 스미스의 수는있다.
지금 당장 그를 호출 할 수 있습니다.
>> 어쩌면 두 단계 한 단계를 갔다, 그러나 단계 상수
운이 좋았어 경우.
그리고 솔직히 말해서, 우리는에보고 월요일 동기생
두 번 연속 꽤 운.
그리고 참으로 일정 하였다 하한 시간
문제의 알고리즘을 찾기위한 그 닫힌 뒤에 번호 50
문.
>> 자, 옆으로, 당신은 발견 할 경우로 모두 큰 O, 상한이
오메가, 낮은 바인딩 즉 동일한 하나의
같은 식이다 괄호, 당신도 할 수 있습니다
그냥 멋진 될 말 뭔가 세타에
n 또는 다른 값의 세타.
그건 그냥 때 큰 의미 O와 오메가는 동일합니다.
이제 선택의 종류는?
의이 새로운 어휘를 사용하자.
선택 정렬에서는 어떤 일이 우리를했다 다시하고 다시하고 다시?
나는 앞뒤로가는 목록, 누구를 찾고?
가장 작은 수입니다.
>> 그래서 얼마나 많은 단계 방법 많은 비교는 I를했다
파악하기 위해 확인해야하는 사람들 리스트에서 가장 작은 요소였다?
n은 마이너스 1, 오른쪽?
난 그냥 난 일을 시작하는 경우 때문에 주어진 내가 그 사람이나 그 여자를 비교하기 시작,
그 사람이나 그 여자, 그 후 그녀, 그 사람이나 그 여자, I 또는
요소 만 페어링 할 수 있습니다 함께 N 마이너스 1 번.
그래서 선택은 일종의 유사합니다 N 1을 뺀 처음 단계를 반복합니다.
>> 그것은에 데려다 않는 몇 단계 둘째 작은 요소를 찾을?
N 마이너스 2, 난 때문에 바보 인 나는 같은 사람보고 계속하는 경우
다시 나는 이미 그를 선택한 경우 혹은 그녀의 자신의 장소에 넣어.
그리고 세 번째 단계, n은 마이너스 3, 다음, n은 마이너스 4.
우리는이 패턴을 보았다 이전에, 실제로
선택 정렬과 유사 바인딩 상부가
의 N 우리가 그 요약을 할 경우 제곱.
그 하한, 선택 정렬은 무엇입니까?
최소한, 얼마나 많은 시간을 반드시 선택 우리는 월요일에 정의 된 정렬이 걸릴?
두 가지 옵션을 제안한다.
아마 이전과 같이, N입니다.
어쩌면 그것으로, 제곱 N 것 상한으로 지금이다.
>> 청중 : N 제곱.
스피커 : 제곱 명.
왜?
>> 청중 : 당신은 가지고 있기 때문에 [INAUDIBLE] 정의합니다.
>> 스피커 : 그렇지.
나는 선택의 종류를 정의 이상으로 꽤 순진, 계속,
가장 작은 요소를 찾을 수 있습니다.
가장 작은 요소를 찾아 다시 이동합니다.
의 어떤 종류의가 없습니다 이 점에서 최적화
나를 후 취소 할 수 있습니다 단지 N 정도 단계.
그래서 실제로 선택 정렬 N의 오메가 제곱.
>> 내가 찍은 삽입 정렬, 어떻 나는 주어진 한 후, 나는 그를 풍덩 사람
혹은 그녀의 오른쪽 자리에?
그럼, 두 번째 사람에게 진행 바로 이곳에서 그 사람이나 그 여자를 풍덩.
그런 다음 사람은 풍덩 그 사람은 바로 이곳에서.
이 매우 것을 알 선형은, 말하자면.
나는 해요, 직선 해요 앞뒤로 않을,
난 절대 정말 다시 찾고, 그러나 한 내가 그를 삽입 할 때 무슨 일이 일어나고
의 시작 부분에 그녀의 또는 목록 우리가 월요일에했던 것처럼?
무슨 일이야?
그래?
청중 : [들리지].
스피커 : 그래, 그 속셈인가?
당신은 기억 할 수 급우들은 경우
어떤 운동을하고 있었다 자신의 발, 즉 작업이었다.
그래서 만약이 삼명 여기에 있었고, 새로운 사람은이 방법을 통해 지배
이 같은 긴 무대에서, 물론, 그는 또는 그녀는 끝까지 갈 수있다.
그러나 우리는 무슨 생각을하는지 컴퓨터 메모리 어레이
이 사람들은 가고 이상 셔플해야합니다
그 사람을위한 공간을 확인합니다.
그리고 그 n은 마이너스 1 shufflings, n은 음이 shufflings, N
마이너스 3 shufflings은 가지입니다 하지 내 앞에, 내 뒤에 발생
이전과 같이, 어떤 의미에서.
이제 옆으로, 등 당신은 온라인으로 볼 수도
당신에 대한 주위 파고 시작하는 경우 종류는 너무 많은 다른 사람있다
그들을 밖으로이 일부 다른 사람보다 더 나은.
사실, bogosort는 하나입니다 즉, 조회 재미 가지입니다.
Bogosort는 세트를 취득 숫자 또는 한 벌의 카드를 말한다
무작위를 섞고, 그리고 검사들은 정렬하는 경우.
없는 경우에, 다시 않습니다.
그렇지 않으면 다시한다.
믿을 수 없을만큼 바보.
>> 그리고 실제로, 당신은 읽는다면 위키 백과의 글을 추천,
별명은 바보 일종이다.
그것은 결국 작동합니다, 희망, 충분한 시간을 주어,
하지만 시간의 양 꽤 시간이 걸릴 수 있습니다.
내가하자 수 있다면 속도 것들 그래서 이전 메리 베스의 예에서 최대,
몇 가지 요소를 가짐으로써, 하지만 둘 이상의 프로세서.
두 사람이, 당신이 경우 나 실까하지.
방법에 대한 하나 여기에, 그리고 의가 아무런 일을 봐야 ...하지하자?
저기 아무도?
확인을 클릭합니다.
검은 색 당신 셔츠, 그래, 아래에 제공됩니다.
좋아, 당신의 이름은 무엇입니까?
>> 청중 : 피터.
>> 스피커 : 무엇입니까?
>> 청중 : 피터.
스피커는 : 피터, 데이비드, 당신을 만나서 반갑습니다.
좋아, 우리가 여기에 베드로가 당신 경우 여기에 테이블에 가고 싶어.
그리고 당신의 이름은 무엇입니까?
>> 청중 : 엘레나.
스피커 : 엘레나.
OK, 만나서 반갑습니다.
엘레나는 피터를 만난다.
피터, 엘레나.
그리고 우리는 앤드류가 필요합니다 여기로 잘 부탁합니다.
그리고 당신의 도전은 것입니다 한 벌의 카드를 정렬 할 수 있습니다.
그리고 익숙하지 않은 경우, 갑판 카드를해야 궁극적으로
같은 작은 선물을 정렬 할 수 이것은 우리가 다음, 클럽을 볼 수있는 곳
스페이드, 그 마음과 하나 에이스부터 다이아몬드,
왕까지 모든 방법.
>> 카드는 내가 당신에게 줄거야 양 (52)이 될 것입니다.
우리는 유사에 갈거야 잠시 시간을.
우리는 앤드류를 던질거야 여기에 화면에,
이 작업을 수행 할뿐만 있도록하면 볼 수 있습니다.
그리고이 모든 것을 모든 더 볼 수 있습니다
이 내가 아마존에있어 카드입니다.
그래서 그들은 무작위로 이미 분류, 우리는 당신을 시간이 될 것입니다.
그리고 우리는에 갈거야 실제이 시간 유지
그래서 우리는 당신을 압박 해 볼거야 그렇지 않으면이 지루한 얻을 것이다 때문에
신속.
당신은 52을 정렬을 진행 할 수 있다면 지금 함께 몇 가지 방법을 통해 요소.
>> 그리고 또, 같이 우리는이 시계 사람은 결국 무엇을, 어떻게
명백한을 생산하는 것입니다 결과는 정말 생각
그들이 어떻게 각각 그 일을하고, 어떻게 당신이 그것을 설명 할 수 있습니다.
다시, 이러한이므로 모든 프로세스, 알고리즘
인간으로 당연한 우리가 걸릴 수있다.
그러나 당신은 아마 긴 했어 직관, 오래 전에도
복용에 대한 생각 컴퓨터 과학 수업 당신에게
직관이 있었다 수 있습니다 이는이 같은 문제를 해결합니다.
그러나 일단 당신이 인식 패턴과 시작
와 같이 공식화 이러한 문제를 해결하고,
당신은 당신이 많은 해결을 찾을 수 있습니다 더 재미 있고 훨씬 더 복잡
신속하게 문제.
그래서 청중 사람, 무슨입니다 알고리즘의 적어도 하나의 원소
이 곳에서 사용하고 있는지?
>> 청중 : [들리지]
스피커 : 무엇입니까?
청중 : 정장으로.
스피커 : 정장으로.
그래서 첫째 그들은 클러스터링 아르 다이아몬드의 모두 함께
그것은 전부를 보인다 함께 보인다 마음,
등, 존중하지 않고 카드의 숫자.
그리고 지금은 예를 들어, 표시, 숫자를 정렬합니다.
아주 좋아.
>> 좋아,에 무슨 일이 일어나고 있는지 여기에 최종 단계가 될?
우리는 네 개의 정렬 된 정장, 일단 무엇을 우리가 네 더미에 어떻게해야합니까
하나를 달성하기 위해 아주 간단하게, 갑판을 분류?
그래서 우리는 다시 병합해야합니다.
>> 그래서 재미있는 아이디어가 있다는 것을 다시 daresay도 매우 직관적이다
당신은 때렸다 결코 있습니다 경우 그것에 라벨의 종류.
분할의 근본적인 개념 문제가되지 절반이 시간에,
하지만 적어도 네 조각으로.
거의 해결 기본적으로 동일한 문제
서로 격리에서, 다음 결과를 합병.
그리고, 우수는 다.
좋아, 큰 라운드 박수, 경우 우리는 할 수 있습니다.
>> [박수]
>> 스피커 : 나는 당신이거야 아무 생각이 이와 함께 할, 그러나 여기 당신은 간다.
정말 감사합니다.
그럼, 이분을 보자 및 팔초,
당신은 당신의 친구에 도전하고자합니다.
무엇 다음에가는 이 뺏을 수
우리는 더 일반적으로 활용할 수있는?
음, 다시 생각 숫자의이 배열,
및 일부 지금 다시 생각 우리가 과거에 작성한 의사,
이는 대한 의사이었다 전화 번호부 문제를 해결.
이에 의해 의사의 I에서 보다 체계적인 방법을 열거
나는 매우 직관적 어떻게했는지 설명하는 전화 분할 알고리즘의 인간
반 책은, 반복, 반복, 반복 내가 찾을 때까지 마이크 스미스 같은 사람,
그 전화 번호부에서 실제로 경우.
>> 그러나 나는 가지 내가 뭐라고 부를 사용 여기에 매우 반복적 인 접근 방식,
특히 예고 라인 8 및 11 행.
사람들은 반복의 증거 접근 방식, 루프 방식,
즉 정확히 때문에 그들이 유도하는 행위.
그 라인 모두에 가자 선 셋, 그리고 당신이 할 수있는 가지
에 그 생각을 당신의 루프 인 것으로 마음의 눈.
이 단계로까지 돌아 가야을 말하고 삼 반복, 다시, 다시,
다시.
>> 그러나 우리는 핵심 아이디어를 어떻게 활용하는 경우 여기에 우리가 지난번했다는 것을,
8 행을 단순화하고 라인 (11)과 이웃
그냥, 노란색 등.
그것은 근본적으로 단축 아니에요 매우 많은 의사,
하지만 근본적으로 변하고 내 알고리즘의 특성.
내가 지금 말하는거야 7 단계에서, 10 단계에서,
마이크를 검색하는 것입니다 동일한 방식으로,
그러나 다만 왼쪽에서 절반 오른쪽 절반.
>> 따라서 다시 말해서, 만약 나는 단계 일에서 시작
중간에 오픈 전화 번호부를 데리러 전화 번호부의, 이름을보고,
스미스는 사이 인 경우 이름의, 마이크, 다른 전화
스미스는 이전 책의 경우, 일곱 단계 책의 왼쪽 반으로 마이크를 검색합니다.
하지만 가지 느낌 그것은 바로, 매달려 날 떠나?
노란색, 인 명령,하지만 난 어떻게해야
왼쪽에 마이크를 검색 전화 번호부의 절반?
나는 어디 있나요 알고리즘가 어떤 I
마이크 스미스 같은 사람을 검색 할 수 있습니다?
글쎄, 우리의 얼굴을 쳐다보고.
말 그대로 동​​일한을 사용할 수 있습니다 프로그램은 효율적으로 정상까지가는
다시하고 다시 실행 코드의 같은 라인.
>> 그래서이 느껴야한다하더라도 순환 정의의 비트처럼
어디 사람이야 대답하고 그저 요청에 의한 질문
다시 같은 질문 같은 왜, 왜, 왜?
우리가 하드 코딩했기 때문에 현실은 특별한 몇 줄, 4 단계,
, 경우, 단계 12 인하는 효과적으로 다른 지점입니다
우리는 이러한 임시 방편의 대책을 가지고 있기 때문에, 이 알고리즘은 종료됩니다 경우 우리
마이크를 찾거나 우리가하지 않으면.
하지만 지금은 7 단계 및 10에서, 우리가 우리는 재귀 알고리즘을 호출합니다.
그리고 재귀은 참으로 강력한 아이디어 즉, 처음에 작은 굽힘 마음이야
다음과 같이 우리가 지금 적용 할 수.
>> 마지막으로 정렬됩니다 정렬 병합이 우리는 공식적으로 적어도 클래스에서, 봐.
그리고 그것은 근본적으로 다르​​다 확실히 그 마지막 세, 그리고에서
마지막 네 우리는 bogosort을 포함합니다.
여기에 병합 정렬의 의사입니다.
n 개의 요소의 입력에, 그래서 주어진 경우 크기 n의 배열은, N은 2 미만이면
돌아갑니다.
그래서 내가 왜해야합니까 정신을 먼저 확인?
나는 당신을 손 경우 의미입니까 길이가 n 개의 배열이 2보다 작?
그것은 이미 오른쪽 분명히 분류이야?
목록은 하나가 있으므로 사소하다 하나의 요소,
이 때문에 분류 이 유일한.
또는, 의미의 사이즈는 제로이다 정렬하는 것도 자연, 그래서이 없다
그것은 정렬됩니다.
잘못이 그냥 아무것도 없습니다.
그래서 우리의 소위 기본 케이스입니다.
>> 즉 정신에 유사하다 우리는 마이크와 무슨 짓을합니다.
마이크의 전화 번호부에있는 경우, 그에게 전화.
그는이 아니라면, 포기.
그것은 소위 기본 사건, 확인하십시오 하루의 끝에서이 알고리즘
특정 상황에서 중단됩니다.
>> 그러나 여기에서 믿음의 도약, ​​다른 지금이다 , 소자의 좌측 절반을 정렬
다음 오른쪽 정렬 요소의 절반
다음 정렬 반을 병합.
그 느낌이 어디 그리고 여기 등 우리가 해왔하고 있습니다.
나는 정렬 할 요청했습니다 N 요소, 그리고 난
정렬하여, OK, 그것을 할 말 왼쪽과 오른쪽을 분류.
그러나 나는 일을 말하고 다른 것은,이
보인다 핵심 주제는 지금까지 직관에,
병합의이 세 번째 단계가있다.
어떤 심지어 비록 정신 너무 바보 같다
같은 단지 물건을 병합 함께 보인다
을 향한 중요한 단계가 될 수 있습니다 이 문제의 재 조립이
반 궁극적으로 나누었다.
>> 그래서 당신은 거 야, 이렇게하자, 일종의 병합 또 하나의 데모 유머 나,
그냥 그래서 우리는 몇 가지가 숫자와 함께 작동합니다.
나는 팔 스트레스를 교환 할 수 있습니다 팔명에 대한 공?
좋아, 어떻게 네 당신은 세 당신에 대한 이 섹션, 다섯, 여섯, 및하자에
7, 8, 최대 어서 않습니다.
OK 예, 확인을 클릭합니다.
마이너스 8, 거기에 우리가 간다, 플러스 1.
우수.
모든 바로 어서하자 빨리 당신에게 번호를 제공합니다.
두 번째, 세 번째, 네 번째, 5 번, 여섯, 일곱, 여덟.
나는 제대로 이번에 팔을했다.
>> OK, 그래서 당신이 할 수있는 경우 진행하고, 의 원본으로 정렬 할 수
우리가 어제 한 것으로보고되는 이처럼, 당신은 상관 없어합니다.
그리고의 테이블 앞에 그것을 할 수 있습니다.
좋아, 그래서 일종의 병합합니다.
이 일어나고있는 곳이다 재미의 종류를 얻을 수 있습니다,
나는 나 자신을주는 것 때문에 너무 적은 정보 오늘.
>> 그래서 일종의 우선 병합 N 개의 요소의 입력에서,
그리고있어 분명 2 개 이상이며 팔은, 그래서 내가 할 수있는 좀 더 작업을해야합니다.
그래서 지금 정신적으로 우리 클래스로 다른 지점에있다,
이는 세 단계를 의미한다.
첫째, 정렬해야 요소의 좌측 절반.
그래서 내가 어떻게이 일을 가야합니까?
글쎄, 난 가지를에 갈거야 정신적으로 여기에 목록을 분할,
당신은 필요 없어 물리적으로 이동하고 난
에만 초점을 맞출 것 여기 소자의 좌측 절반.
그래서 정렬에 대해 어떻게 가야합니까 이제 크기 넷의 목록?
내 알고리즘은 무엇입니까?
우선 검사가 아니,이 n보다 작은, 그래서 나는 다시 다른 블록으로 진행합니다.
정렬 요소의 절반을 떠났다.
>> 그래서 지금 다시, 정신적, 이것은 어디
당신이 많이 발생해야 정신 역사, 만약에 당신.
지금은 왼쪽 정렬 해요 왼쪽 절반의 절반입니다.
좋아요, 지금은 내 같은 병합 전화 정렬 알고리즘, 채 2를 n은?
아니, 두 개, 그래서 정렬해야 좌측 절반과 우측 절반.
그래서 여기에 우리는 왼쪽 반을 정렬, 이동합니다.
그냥하지 않습니다 앞으로 한 걸음.
당신의 이름은 무엇입니까?
>> 청중 : 대런.
>> 스피커 : 댄.
댄은 앞으로 강화하고있다.
>> 청중 : 대런.
스피커 : 대런, 수행.
당신은 대런 또는 단 말을 했습니까?
>> 청중 : 대런.
>> 스피커 : 대런.
OK, 대런 강화하고있다 앞으로 그는 지금 정렬됩니다.
그리고이 거의입니다 공허한 주장, 오른쪽?
정말 달성 될하지 않는 것 아무것도하지만의 진행하자.
지금 나에게 맞는을 정렬 할 수 요소의 절반.
당신의 이름은 무엇입니까?
>> 청중 : 누가 복음.
>> 스피커 : 누가 복음.
자, 앞으로 단계.
완료, 나는 누가 복음을 분류했다.
왼쪽 절반은 지금 분류되고 오른쪽 절반은 지금 정렬
그러나 다시, 여기에 중요한 단계가있다.
내가 다음에 어떻게해야합니까?
정렬 반쪽을 병합합니다.
이제 우리는 할 겁니다 앞뒤로 이러한 방법으로 모든 사람,
내가 가지 필요 때문에 약간의 스크래치 공간입니다.
그것은 거의 이러한처럼 사람은 테이블에 있습니다,
나는 약간의 공간이 필요 그들을 주위로 이동합니다.
그래서 병합거야 봄으로써 너희들
왼쪽 부분과 오른쪽 절반에.
그리고 분명히 먼저 누가, 왼쪽 절반 오른쪽 절반?
그래서 오른쪽 절반은, 그래서 이상 누가 복음을 이동할 수 여기 대런의 원래의 위치로.
그리고 지금은 자신의 왼쪽 절반을 병합, 대런 바로 이동하는 것입니다.
>> 그래서 거의 같은 느낌 거품 정렬 효과
하지만 내 기본 알고리즘, 이 때 매우 다른.
가지를 얻을 곳하지만 지금이다 조금 귀찮은 당신 때문에
정신적으로 되감기해야 나는 곳을 떠 났죠.
난 그냥 정렬 반쪽을 병합했습니다, 이는 내 알고리즘 어디 뜻이에요?
나는 바로, 오른쪽 절반을 정렬해야?
>> 말 그대로, 되감기 경우 비디오에, 당신은거야
우리는이에 도착 볼 누가 복음과 대런의 포인트
왼쪽으로 정렬하여 왼쪽 절반의 절반입니다.
그 다음 우리는 그 합병 정렬 반쪽, 어떤
다음 단계는 정렬을 의미합니다 왼쪽 부분의 오른쪽 절반.
좋아, 이렇게하자 보다 신속하게이 작업을 수행.
좋아, 여섯, 내가 주장하는거야 이제 앞으로 어서 분류되어 있습니다.
당신의 이름은 무엇입니까?
>> 청중 : 아드리아누.
>> 스피커 : 아드리아누.
아드리아누는 현재 정렬됩니다.
그리고 당신의 이름은 무엇입니까?
>> 청중 : 알렉스.
>> 스피커 : 알렉스는 이제 정렬됩니다.
왼쪽 반, 오른쪽 절반, 마지막 단계는 무엇인가?
병합합니다.
아주 사소한, 그래서 난 육에 병합하는 것,
한 걸음 물러나서, 팔은 단계를 다시 받아.
그리고 지금이 예고 유용한 테이크 아웃, 무엇을
지금의 왼쪽 부분에 대한 사실 목록에 관계없이 우리가 시작하는 방법?
이 정렬됩니다.
>> 지금은 정렬 아니에요 사물의 큰 계획,
그러나 독립적으로 정렬 나머지 절반의.
내가 계속한다면 이제 어떻게 단계 나는에 어디로 이야기가 어떻게 시작 되감기?
지금은 오른쪽 절반을 정렬해야합니다.
그래서 지금 우리는 돌아 오는 길에있어 이야기의 시작,
그리고 좀 더 빠르게이 작업을 수행 할 수 있습니다.
그래서 정렬거야 전체 목록의 오른쪽 절반.
다음 단계는 무엇입니까?
오른쪽 절반의 왼쪽 절반을 정렬합니다.
의 왼쪽 절반을 정렬 오른쪽 절반의 왼쪽 절반입니다.
그리고 당신의 이름은 무엇입니까?
>> 청중 : 오마르.
>> 스피커 : 오마르, 수행, 앞으로 단계.
왼쪽 절반이 정렬됩니다.
그리고 당신의 이름은 무엇입니까?
>> 청중 : 크리스.
>> 스피커는 : 크리스, 조치를 취할 앞으로, 당신은 지금 분류되어 있습니다.
이제 중요한 단계는 무엇입니까?
병합합니다.
그래서 한 자리에 병합하는 것입니다 여기, 당신이 다시 조치를 취할 수 있다면,
그리고 세에 가고 병합 단계를 다시 받아.
그래서의 좌측 절반 오른쪽 절반은 지금 정렬됩니다.
솔직히,이 알고리즘은 우리 같은 느낌 이전보다 훨씬 더 많은 시간을 낭비하고,
우리는 실시간으로 이런 짓을하는 경우, 우리는거야 집에 사 가지고가는 요리가 될 것 무엇을 참조하십시오.
지금 나는 여기, 바로 어디로 우측 절반의 반
내가 가서 왼쪽 절반을 정렬 할 수 있습니다.
앞으로 단계, 당신의 이름은 무엇입니까?
청중 : 램지.
스피커 : 램지는 이제 정렬됩니다.
당신의 이름은 무엇입니까?
>> 청중 : 마리나입니다.
>> 스피커 : 마리나는 현재로 정렬됩니다 물론, 당신은 앞으로 한 걸음을합니다.
여기에서 중요한 단계는 지금​​ 난, 병합된다 내이 목록에서 뽑은 것,
왼쪽과 오른쪽.
다섯, 첫번째 올 것입니다 일곱 다음 올 것입니다.
그리고 다시, 이것은 의도적 인 것입니다.
그들이 복용하고 있다는 사실 앞뒤로 단계
표현하는 것을 의미한다 즉, 우리는 할 수 없습니다 쉽게 장소에이 알고리즘을 수행
거품 정렬 및 선택 정렬로, 및 삽입 정렬 어디서 단지
명을 교환 유지했다.
말 그대로 일종의 필요 스크래치 종이의 어떤
이 사람들을 넣어 나는 병합을 수행하는 동안,
그리고, 나는 다시 제자리에 넣어 수 있습니다.
내가 사용하고 있기 때문에 그 열쇠 새로운 자원, 공간뿐​​ 아니라 시간입니다.
>> OK,이 놀랍습니다.
왼쪽 절반은 오른쪽 절반은, 정렬 정렬, 지금 키 병합하는 단계를 포함한다.
어떻게하면이 문제를 병합하지?
당신이 따라 준다면 그래서 내 왼쪽 손과 오른쪽,
나는 내 왼쪽 손을 가리 키도록하겠습니다 왼쪽 부분에서, 내 오른손
오른쪽 절반에, 지금은에있다 병합하는 단계에 의해 단계를 결정할 수 있습니다.
누가 분명히 먼저?
번호 하나.
그래서 여기에 와서, 여기에 우리의 스크래치 패드입니다.
그래서 지금 한, 통지 번호를 내 오른손으로 무엇을 할 것입니다,
내 오른쪽 하나를 이동하는거야 세 번째를 가리 키도록 스텝 오버,
지금은 확인해야 같은 의사 결정.
그리고 실제로 마우스 오른쪽 스탠드 누가 여기에 당신이 할 수 있다면 앞에,
이것은 우리 스크래치 패드이기 때문이다.
누가 다음에 온다?
우리는 두 번째와 누가 복음을 크리스 세 번째로.
분명히 누가 복음, 수 두 사람은, 그래서 당신은 이리와.
>> 하지만 내 왼손은 지금 것입니다 대런를 가리 키도록 증가 될,
여기에 키가 멀리 데려 가라 병합, 내가이 일을 계속하려고 해요,
분명히, 당신이 경우 종류 의 논리를 따르십시오.
하지만 내 손은 결코 거꾸로 갈,
어떤 난 오직 이동하고있어 의미 내 병합 프로세스 왼쪽,
그리고 그 핵심이 될 것 잠시 우리의 분석.
>> 그래서 지금의이 빠르게이 문제를 마무리 할 수​​ 있습니다.
그래서 세 다음에 온다 다음 네 다음에 온다
지금은 다섯 여섯, 다음, 다음 제공 칠하고 마지막으로 팔과.
가장 느린 알고리즘 같은 느낌 아직 아니라 실제로 만약 우리
같은 종류의에서 실행 클럭 속도, 너무
같은과, 이야기 이전과 시계를 새기는.
왜?
음, 보자 최종 결과보고.
>> 저를 보자, 이제 여기에 다시 가자 시각적 데모를 끌어
우리가 한 일.
이에, 여기에서 확대 여기 페이지에서 파이어 폭스를 말하고
우리는 대기하도록 이 상자까지하자
, 거품 정렬 말을하는과 우리는 지금 잘 익숙
또 다른입니다 선택 정렬, 매우 간단 하나,
지금 오늘날의 병합 정렬하는 우리의 클라이 막스 엔딩이 될 것입니다.
그것은 더 이상 그렇게했다 이유 여기에 인간과 나 구두입니다,
분명히, 나는 모든 단계를 설명하고 있습니다.
그러나 단순히이 훨씬을 실행할 경우 같은 우리가했던 거품 정렬 및 선택
종류뿐만 아니라 시각적으로 시계 얼마나 더 효율적으로
이 레버 리징 분열과 정복
있어 데이터 세트에 적용 할 수있을 때 심지어 크기 팔, 그러나 더 많은,
훨씬 더 큰.
난 당신에 의해 정렬면을 병합 제공 이러한 다른 알고리즘 측면.
이 고통받을 것입니다 신속하고 엔딩
특히 클라이 막스 아니다 그들은 단지 분류 끝낸다.
그러나 키는 것입니다 빼앗아 정렬 방법을 훨씬 더 빨리 병합 보일
당신이 난 생각하지 않는했다 그냥 가지 당신과 함께 장난.
우리는이 일을 마지막으로 할 경우, 의이를 다시 보자, 그냥 돌아가요
와, 거품 정렬을 선택 그냥 심심해서,
이제 삽입을 선택할 수 정렬 그냥 좋은 측정을위한.
그리고 이번에는 다시하자 병합 정렬을 선택하자
실제로 옆에 이러한 측면을 실행합니다.
>> 그리고, 사실, 우연이 아니다.
내가 효과적으로했던 것은 제가했습니다입니다 다시 반으로 내 입력을 분할
다시, 다시.
그리고 당신이 할 수있는 경우에만 너무 많은 시간을 거기에 반으로 입력을 나누고, 왼쪽
오른쪽.
어떻게 우리가보고 계속 식이다 그 반으로 분할 설명
또 다시, 그리고 또 다시?
>> 관객 : N의 로그를 취합니다.
>> 스피커는 : N의 로그를 취합니다.
그러나 다른 하나의 중요한 단계가있다, 이 알고리즘은 로그 N 단계되지 않습니다.
이 로그 만 N 된 경우 단계, 우리는 같은 문제에있을 것입니다
우리가 할 수없는 경우 이전과 안부 정렬.
당신은 최소한 n 개의 요소로보고있다 확인 n를 요소가 분류되어,
그렇지 않으면 믿음의 도약이다.
>> 그래서 최소한의 로그 N 단계, 그러나입니다 이 키를 병합 단계에 대한 어떤
나는 합병 내 왼쪽 절반과 오른쪽 절반은 무대를 가로 질러 걸어?
그 병합하려면 몇 단계인가?
그것은 N,하지만 난 그냥하지 않았다 마지막으로 병합합니다.
각 이러한 중첩 호출 각각에 그 중첩 된 병합, 나는 여전히 분류.
나는 그때이이 두 사람을 병합 얘들 아, 다음이 두 사람 등등.
>> 그래서 다시, 다시 병합 않았다.
몇 번?
그래서 때마다 내가 나눈 목록은 반으로, 나는 병합을했다.
병합을 반으로 목록을 나눕니다.
리스트 분할 그렇다면 로그 N 번 수행 할 수있다,
와 합병은 궁극적으로 N 소요 단계는 무슨 일이 이제 상부 수 있습니다
실행에 바인딩 우리의 알고리즘의 시간은?
n 여기서 n 로그인합니다.
>> 그리고 사실, 그게 무슨이다 우리는 여기에서 달성했습니다.
그래서 당신은 시각적으로 볼 때 느낌 그 세 가지가 나란히 실행
n 여기서 n에 대해 제곱 N 로그 N에 대해 제곱.
우리가 볼 수 기본적으로 어떤, 오늘날 그러나 미래뿐만
훨씬, 훨씬 더 빠릅니다.
이 사람에 대한 갈채를, 나는 스트레스 공을 갚아 주실 것이다.
의 오늘 여기에 휴회하자, 그리고 우리는 월요일에 당신을 볼 수 있습니다.