[Powered by Google Translate] [주 3 계속]
>> [데이비드 J. Malan - 하버드 대학교 (Harvard University)]
>> [이 CS50입니다. - CS50.TV]
>> 괜찮아요. 다시 오신 것을 환영합니다. 이 CS50이며,이 주 (3)의 끝입니다.
>> 그럼 그 익숙 지난 년 동안 하버드는 혁신 연구소라는 것을 시작
HBS의 캠퍼스에서 강을 건너 훌륭한 건물에 자리 잡고 있습니다 또는 I-연구실,
그 대학 학생, GSAS 학생, 모든 전체 캠퍼스의 학생들에 열려
교수를 포함하고 혁신적인 일에 일을 함께 할 수있는 장소,
특히 기업가 일
당신과 0 또는 더 많은 친구들이 기업가 뭔가를하고 생각하는 경우
이 클래스 중,이 클래스 후, 또는 초과 중.
>> 그래서이 J 기간 동안 할 일 중 하나는,이 여행이다
뉴욕, 실리콘 밸리 인 중 하나입니다 중 하나입니다.
공간은 매우 한정되어 있지만 MBAs과 어깨에 문지르 할 수있는 기회
및 캠퍼스에서 실제로 대학원 학생들은 그 각각의 분야에서 시간을 보내
, 신생를 채팅 기업가를 채팅하고 좋아요.
관심이 있다면,이 URL을 여기에 확인하시기 바랍니다.
또한 온라인 슬라이드에서 사용할 수 있습니다.
>> 우리는 톤 다운 하우스 오디오를 조금이라도 할 수 없나요?
이 금요일 점심 시간에 우리와 함께하려는 경우, 화재 및 아이스의 1시 15분 오후은 거기로 향할하시기 바랍니다.
경우 죄송는 양식은 이미 자네가 도착할 때 쯤엔 가득 차 있습니다.
그러나 우리는이 전통 이후를 계속합니다.
>> 오늘 우리는, 우리가 해결할 수있는 다양한 문제의 높은 수준의 토론을 계속
적어도, 코드와 더 많은 아이디어 오늘날 훨씬 더 초점.
그래서, 우리는 반으로 전화 번호부를 찢고 때 다시 주 0 생각
의 목적은 뭔가를 보면 조금 극적인했다
하지만 검색은 반드시 할 필요는 없습니다하는 지점을 보내려면
당신이 생각 하듯이 첫 눈에 같은 명백한.
일반적으로 문제 해결이 반드시 최선의되지 않을 수 있습니다 -
가장 눈에 띄는 솔루션은 반드시 가장 좋은 건 수 있습니다.
그래서 우리는,이 방에있는 우리 모두가 직감을 가지고, 솔직히,이 전화 번호부를 가지고
대부분 다음, 마이크 스미스를 찾을 때 중간에 시작하고하는 것은 왼쪽이나 오른쪽으로 이동
우리가에 종료 일어난 알파벳의 어떤 문자를 기반으로.
>> 그러나 우리 인간을 위해 촬영 한 간단 아이디어는 오랫동안 부여
정말 마음의 최전선에 와서 시작해야합니다
문제가 훨씬 더 복잡 전화 번호부보다 질수록 때문에,
그 같은 간단 화려한 통찰력은 우리에게 허용하는거야 뭐야
훨씬 더 복잡하고 더 재미있는 문제를 해결하려면,
요즘 이미 승인을 위해 중 몇 가지 우리가 걸릴.
아직 웹 저기 페이지, 구글과 빙과 같은 수십억
그런 식으로 우리 것을 발견 할 수 있습니다.
그래서 가능한 모든 웹 페이지를 검색, 선형 검색을 사용하여 안될 겁니다.
페이스 북은 친구의 친구의 친구이거나 누군지는 말해 줄 수 있습니다
그 역시 요즘 순식간에 겉으로 수행 할 수 있습니다
그들은 사용자의 수백만이 있어도.
>> 그리고 우리가 실제로 규모 문제를 해결하는 방법 궁극적으로 줄일 수 있습니다
아이디어를 오늘 조금 더 주 0을 검토.
우리는이 알고리즘을 다시 실행하지만, 기억하지 않습니다 우리는 주 0이 운동을 할에 한
우리 모두가 서 한 곳, 숫자 1에서 수행
그리고 우리는 함께 숫자를 추가 해제 페어링하여 모든 자기 수를 가지고
다음 갱의 절반은 모든 반복에 앉았다.
그래서 우리는 500 학생들 250-125에 가서 등등.
거기에 우리가 월요일에 말한대로, 강력한 아이디어
이었다 우리는 그 문제의 크기를 두 배로하는 경우
와 정의 또는 EC 10 일부터 모든 아이들은 방으로 돌아 와서 우리에 합류
그래, 우리가 아마 그 전체 집계 그룹을 계산 할 수
루프의 단 1의 큰 반복과 사람들은 아마도 크기를 두 배로 때문에
또는 더블 사이즈보다 조금 더 EC 10의 경우 인치
그래서 우리는, 조금 더 시간을 투자해야
하지만 우리는 400 또는 700 이상의 단계를 지출 할 필요가 없습니다 것입니다.
>> 그냥 좀 덜 추상적이지 방식으로이 그림을 그릴 위해 모두들이 서있다하지 맙시다.
하지만 오늘은 오케스트라에 앉아하도록 선택한 분들이 괜찮 으면, 잘 서
우리가 가장 높은 사람이 어떤 사람인지 사이 알아낼 수 있다면합시다 볼
비교 알고리즘의 이와 같은 일을하여.
당신은 오케스트라, 사과 있지만, 1 단계에서 앉아다면, 일어나,
2 단계 인근 사람과 오프 쌍,
키가 누군지 알아내는, 그리고 짧은 경우 앉아.
그런 다음 반복합니다.
[학생들이 웅성 대는 소리]
>> 좋아요.
좋아요. 하나는 서 남아 있습니다. 이름이 무엇입니까? >> 앤드류.
>> 앤드류, 당신은 오케스트라 섹션에서 가장 높은 사람 오늘입니다.
>> 축하합니다. [박수와 환호] 좋아요. 자리에 앉으 시죠. 그래서 우리는 앤드류를 찾았습니다.
그러나 얼마나 저를 촬영했을 예를 들어, 앤드류를 찾을 수
50 + 정도의 사람들이 오케스트라 섹션에?
나는 매우 간단한 접근 방식을 촬영하고 여기서 시작했을 수 있습니다.
그리고 난 2 사람이 일어 서서하고 난을 비​​교
그리고 제가 약간 짧은 사람에게 말, "그래, 당신이, 앉아"
그리고 내가 키가 사람이 누군지 기억거야.
그럼 난 반복 반복 반복, 그리고 가장 높은 사람에게 기다려
나는 어떤 시점에서, 그들보다 사람이 약간 키를 찾을 때까지
약간 짧은 사람이 그러면 앉아있다.
그러나이 오케스트라 섹션에서 해당 알고리즘에 경우의 N이
데려 갈 그 알고리즘은 얼마나 많은 단계입니까? >> [학생] N.
>> 그것은 최악의 경우에, 말하자면 때문에, 오른쪽, n을 걸릴 거예요
가장 높은 사람은 그냥 무작위로 운로 갈 바로 그 마지막 사람입니다.
따라서 최악의 경우에, 그 알고리즘의 실행 시간은 선형이며, 그것은 N입니다
n은 공간에서 사람들의 총 수, 문제의 크기입니다.
이 알고리즘은 어때?
당신은 모두 당신을 다시 이분의 일 후 일어나서는 사실이 앉아서
당신의 절반 앉아, 당신의 절반이 앉았다.
당신의 n은 여기이 있다면 그 몇 단계 데리고해야하나요?
[학생] N 로그 N. 악화 될 것입니다 >>. n을 기록합니다.
>> 그래서 꽤 로그가 무엇인지 기억하지 않더라도, 로그 N
지금, 그냥이 이등분하고 반턱과 반턱 든 관련 감사드립니다.
이 2 요소 필요가 없습니다. 이 3 요소 수 있습니다.
그러나 문제의 크기는 여기에 시작되는 등 요소의 같은 종류의 반복입니다
하지만 바로 다음 여기, 여기, 그러면 여기에, 간다.
당신은 문제가 작은 물기를 데려 갈 수 없어, 당신은 진짜에 떨어져 구조 중이다
큰 폭발음과 함께 할 때마다 떨어졌다.
그래서 우리는, 12 ½ 또는 13 사람들이 서 그 다음에 25, 50 명의했다
그리고 마지막으로 단지 앤드류가 남은 지위까지 등등 6 ½합니다.
그래서 우리는 N의 로그에 전화를하고, 당신이 다음과 같이 시각화 할 수 있습니다.
선형 알고리즘이 빨간색 선처럼이고, 여기에서이 사진을 기억
노란색 선은 우리가 계산 학생들을 위해 사용했던 거 고요 알고리즘에 의해 계산했다
과거에, 오늘은 성배가이 녹색 선 남아 것입니다
우리가 오케스트라 섹션에있는 사람의 수를 두 배로 있거나 말 곳
이런, 그렇게 큰 거래, 일어나가 전체 방에있는 모든 사람이하지 말자
우리는 대략 여기까지 얼마나 많은 사람들이 두 번, 때문에
1 개 반복이 아닌 문제가 발생했습니다.
>> 우리는 앤드류 또는 사람 앤드류보다 클에서 일어나는 발견 한
중간층 또는 발코니 인치
전화 번호부에서 부여를 위해 우리가 많이 가지고 있다는이 간단한 아이디어 자,
우리가 적용 할 수있는 많은 다른 장소가 있다는 것을 알고 있습니다.
먼저, 사실이 아닌 전문 용어 - 그냥 전문 용어 폭력이나 휘두르는
내가이 사진에 여기 가자.
지금 우리는 N과 N / 2에 대해 얘기하고 다음에 n의 로그
우리가 학기 과정을 통해 의지로 우리는 분명, 가지고 올 수
수학 공식의 다른 종류의 시간을 실행이 일반적인 개념을 설명합니다.
오래 전에 우리가 볼 수 있기 때문에 지금에 대한 컨텍스트를 벗어
이 실제로 대표하는 알고리즘.
>> 하지만 여기주의 선형 N 라인, 직선, 지금 지적 실제로 매우 낮은 것입니다.
우리가 그냥 X 축가 무엇을 나타내는 지 변경에 착시의 일종 이죠
과 Y 축, 그리고 우리가 원하는 방향으로 직선 지점을 만들 수 있습니다.
하지만 지금은 그렇게 보이는 평평 이유
우리가 많이 느린 실행 시간이 그래프에 공간을 확보하기 위해 필요하기 때문입니다.
지금, 인생에서 꽤 많이 알고리즘이 있다는 것을 알고
N 단계 만 더 로그인 아직 더 나은, N 조치를 취하거나하지 않는 중.
따라서 선 위의 N 여기에서 하단 통지에 n의 n 번 로그,이
우리는이 현상이 오래 전부터 무슨 뜻인지 볼 수 있습니다.
그 위의 제곱 습니하고 있으며, 우리는 아직 N 제곱 알고리즘을 보지 못하지만 우리는 간다.
그리고 정말 나쁜 보입니다.
2 더 나쁜 느낌 지수 무언가, N주고있어.
아직, 호기심, 다음 앞서 생각의 일종 경우 N cubed는,이
어떤 종류의 N에 수학, 2한다면 실제로 많은 똑바로됩니다
당신은 지금까지 충분히 축에서 보면 N보다 더 많은 이상은 cubed.
따라서 이러한 축 임의로 X 축에 2~10아르 지금 확인합니다.
>> 그리고 그게 무슨 뜻 이죠?
그 방에서 2 명까지 10 명의 사람을 의미합니다.
문제의 크기, 문맥이 무엇이든 : 그 모든 X 수단입니다.
그리고 수직 축 지금 초 단계의 수의 개수입니다 -
시간의 일부 단위입니다.
그러나가 0 60 0-10 있다는 것을.
그러나 만약 당신이 Excel 또는 일부 차트 소프트웨어의 수도로, 축소의 우리 종류
우리는주의, 200,000에 올라가 그 2와 같은 N에 뭔가
완전히 제곱 n의 실행 시간을 압도 것입니다,
n은 cubed, N 로그 N - 우리가 지금까지 이야기했던 모든 것.
당신은 페이스 북과 같은 것들에 대해 얘기 시작할 때 그리고 아직 캐치입니다
당신은 많은, 많은 사람들은 모든 상호 연결 한 곳,
당신이 사람들을 향한 한 각 누구의은 N의 친구로 많은이있을 수
모든 사람이 세계에서 친구 - 친구의 일종이며, 경우
글쎄, 그 n 번입니다 N 이미 있으므로 제곱 가능한 우정을 보군 그
최소 1 방향, N 제곱 가능 우정 인치
그래서 이미 말하자면, 페이스 북의 소셜 그래프를 검색하는 것이 좋습니다,
수식의 이러한 종류의 표현 할 수 있습니다.
>> 우리는 다시 와서이 훨씬 더 구체적인 할게요
다음 몇 주 동안 지금 들어, 목표
구현 알고리즘이나 코드에 대해 이동하지 않도록 될 것입니다
그 같이만큼 시간을 내 주셔서 결국.
그러나 컴퓨터 과학에 대한 흥미 점은이 분야에서의 지속되는 경우
, CS121, CS124과 같은 수업을 이론 과정 아르 둘 다 복용​​,
이 세상에서 존재하는 문제가 실​​제로 있다는 것입니다
근본적으로, 우리가 아는 한, 빨리 해결 할 수없는
이 그래프의 최악 실제로 제안보다.
따라서 인간은 지금까지이보다 더 할 수있는이 세상에서 열려 많은 문제가 있습니다.
>> 그래서 예를 누른 다음 시작하자.
우리는 너무 어색 비디오에서이에 카메라 숀 투쟁을 보았다.
션이 7 번과 같은 보드에 찾는가 주어 때하지만 현실은,이었다
나는 "이러한 종이 조각 또는 흰색 문 뒤에 어딘가에있다, 그런 말 한걸 기억
"숫자 7. 션, 우리가 찾아."
그리고 감상 할 이상하게 거북 하군요
그는 정말이 문제를 고민했기 때문.
하지만 현실은 션이 방에있는 사람이 수행 할 수 있습니다뿐만 아니라 한이었다.
그는이있을 좀 더 일반적인 사람보다했습니다
그러나 그는 어떤 트릭이 문제가 있었다고 생각
그는 뭔가를 누락라고 생각 했었습니다.
그리고 눈의 수백이 그를 향하고 있다고 도움이되지 않았다.
>> 문제에 대한 입력이 임의의 숫자의 무리 경우하지만 현실은했습니다
하면, 1 등 번호를 알아 보라고 받고 있어요
당신이 할 수있는 최선의 방법은 선형 검색입니다.
왼쪽에 시작, 오른쪽으로 이동하거나 왼쪽으로 이동, 오른쪽부터 시작합니다.
소급하여, 우리가 생각 될 수 있습니다, "숀, 왜 당신은 다른 쪽 끝에서 시작하지 못 했을까?"
음, 7 단지 쉽게, 무작위로 여기 온 수
난 그가 말에 시작하지 않을거야 생각하기 때문에 나는 의도적으로 거기에 넣어.
그래서 가지 상황을 조작하지만, 임의의 기회 (7)에 의해 어느 해놨을 수도있다.
그럼, 오른쪽 끝에서 시작하여 다음 좋겠지 만
하지만 만약 내가 다른 곳에서 7로 이동 다음 해?
그게 문제에 대한 근본적으로 새로운 솔루션이 아니에요 -
한 끝 또는 다른에서 시작 - 당신이 다른 가정을 제공하지 때.
그럼 숀이 숫자를 통해보고 시작, 그는 "5. 그건 여기 없어요."
그럼 그 사람은 여기 가서 19 본, 그는 약 20 초 동안 일시 중지
그 다음에 그는 13이을 열어 다음은 뻔 했지요
여기에 패턴이있을 것하지 않습니다.
이 1, 2, 3, 4 또는 같은 아니 었습니다. 도움이되지 않은 숫자 격차가 발생했습니다.
그리고 나도 종이의 이러한 저렴한 조각을 사용한 사실은 숫자를 덮기 위해서
때문에 종이의 모든 조각을 제거한 경우, 실제로 의도적으로입니다
우리 대부분은, 숀 포함, 아마 종류 macroscopically의 훑어 것이다
칠판에 그리고 "오, 7 거기 분명히"고 말했다. 우리는 즉시 했어요.
>> 그래서, 인간의 뇌는 어느 정도 작동하는 방식 일 수도
하지만 현실에서, 그의 눈 또는 마음이, 오른쪽에서 왼쪽으로 가며 번호를 아마도
밖으로 오른쪽, 중간 왼쪽 - 무슨 일이 생리 학적으로 일이 있었던거야
그 즉시 일어나는 것처럼이 느껴지도록
하지만 아이가 내부적으로 7 찾는 방법 어떤 종류의가 있다고도합니다.
그리고 실제로 지금 우리는 배열과 데이터 구조에 대해 얘기하는
그리고 컴퓨터의 메모리 내부의, 우리 인간이 유일한 것은 할 수
한 번에 개별 메모리 위치에 1을 볼 수 있습니다.
>> 따라서 다른 모든 위치뿐만 아니라 종이의 일부 조각을 은폐 될 수 있습니다
우리는 어쨌든 그것을 볼 수 없습니다 때문입니다. 우리는 한 번에 한 가지 작업을 수행 할 수 있습니다.
따라서이 경우에는, 션의 경우, 우리는 여기에 가서 다음에 우리가 여기 갔다
그리고 우리가 간, 여기, 여기, 여기, 마지막으로 영리한있어
불과의 종류 임의로이 하나를 건너 뛰고도 7 발견했다.
이 사람은 특히 특별 아니 었습니다. 이거 너무 고장이었다.
그러나 그는 결국 7 발견했다.
그러나 지금은 테이크 아웃 정말 당신이 할 수있는 최선의 어떠한 정보를 제공 없을 때이다
무작위로 정렬 된 숫자 이외는 왼쪽에서 시작하거나 오른쪽에서 시작하는 것입니다.
또는 대체, 당신은 무작위로 문을 열 수 있습니다,하지만 다음에 어떻게가 무작위로 의미합니까?
음, 우리가 어찌 여기 시작하는 데 의미를 공식화해야 할
그리고 여기에서, 여기에 이​​동합니다. 숀 아주 잘 했어, 그리고 볼 그냥 재미로했다.
우리는 문제에게 조금 변경하고, 당신이 가만히 있으면 올해의 숀을 표시 무엇입니까 대신한다면?
사람이 무대에 와서 약간 다른 문제를 해결 편
카메라에 게재?
>> 당신들이 매우 이미 오늘 관여했기 때문에가 오케스트라 넘어 가자.
방법에 대한 분홍색에 모자? 이리 오게. 당신의 이름은 무엇입니까? >> 알렉스. >> 알렉스. 좋아요.
그래서 알렉스는 올해 숀되며 향후 몇 년간에 나타납니다
CS50 강의의 가치.
알렉스, 반가워요. >> 저도 반가워요.
당신 손에있는 문제는 당신이 좀 더 쉽게되어 있다는 것입니다
거기에 내가 여기 당신에게 같은 번호를 아르 말하는데,하지만 지금은 정렬됩니다.
이제 당신의 목표는 숫자 7을 찾는 것입니다.
그리고 실제로 우리가이 일을해야 - 부정 행위의 넌 종류를 컴퓨터 하시겠습니까 아니라
무엇을보고 숫자는 잠시 전에 있었다.
분필로이 사실은 모두 많이 도와 줘야하지
하지만 원래 배열이 뭔지 모르는가 가정합시다.
지금 아는 한 당신은 정렬 숫자의 배열을 가지고 있다는 것입니다
그 둘 사이 간격이있는 것, 그리고 목표는 7 번을 찾을 것입니다.
어떻게,되는 합리적인 인간은 숫자 7을 찾는 것에 대해 갈거야?
>> 낮은 가격순에서 이동? 좋아요 >>. 낮은 가격순 이동합니다.
그리고 그것들을 찢어하지 않습니다. 우리가 그들을 재사용 할 수 있도록 그냥 올려 들어 보자.
그래, 그럼 1. 기다립니다. 당신이 계속하기 전에, 그 분명 잘못 1이었다.
그래서 우리가 옆에 무슨 생각을하고있어? 다음 계획은 무엇입니까?
다음. 좋아요 >>. 다음. 좋아. 그래서 잘못된 3. 다음 계획은 무엇입니까?
가보 거라. >> 좋아. 가보 거라. 5.
그럼 계속하고 있으며, 내가 후대를 위해 당신에게를 건네 보자.
7. >> 좋아요. 아주 좋아. 숫자 7을 찾았습니다. [박수]
그럼 좋은했지만, 숀도 수 7 발견했다.
그리고 당신이 정말 정보의 추가 조각을 이용하지 않은 주장
이는 숫자가 정렬된다는 것입니다.
그래서 우리가 더 잘할 수 있습니까? 여기 방법은? 네, 다시 인치
[학생] 이진 검색 할 수 있습니다. >> 나는 이진 검색이 뭔지는 전혀 감이 없습니다.
>> [학생]는 중간에 시작합니다. >>는 중간에 시작합니다. 좋아요. 그럼 우리가 할 수 있나 보자.
당신이 중간에서 시작을시키는 대신다면, 가서 중간 문을 엽니 다.
이 중 8 야하므로 임의로 하나를 선택해야 할 것
약간 왼쪽이나 오른쪽으로. 좋아요. 7! [박수] 아주 좋네요.
그래,하지만 우리는이와 함께 어디로 갈거야?
우선은 여기 시작했습니다 넥타이를 부러 가정
그 똑같이뿐만 아니라 일어날 수있는 일 때문입니다.
우리는 7가 있다는 사실을 알게되어 일. 그래서 13입니다.
들은 정렬 된 경우 그래서 우리는 그냥 중간에 시작
최적의 다음 행동은 뭐야 갔었을거야?
왼쪽 이동합니다. 그리고 여기에 다시 전화 번호부 예를 제공합니다.
13 여기 우리는 목록이 정렬되어 알고있는 경우는,
그리고 종이의 이러한 조각의 모든 이제 우리에게 흥미 아르
우리는 이미 7 왼쪽에 있어야합니다 알고 있기 때문에
이 번호는 정렬하고 13를 발견하는 경우.
>> 그래서 여기 다음 계획은 뭐죠? >>는 왼쪽으로 이동합니다. >> 그래, 좋아.
헤이, 헤이, 헤이, 잠깐만 요 - 그럼 왼쪽으로 이동합니다. 그건 반칙이야.
그래서 7을 발견하지만, 우리가 적용된 알고리즘은 무엇입니까?
중간에 시작합니다. >> 좋아. 그래서 같은 생각의 논리적 확장은?
아, 그냥이에. 정확히 >>. >> 그래서 여기 시작합니다. >> 좋아.
이제 우리는 다시 왼쪽으로 약간 갔다. 은 3입니다.
그러나 흥미로운 테이크 아웃은 지금 당신이 신경이없는인가요?
이 2. >>이 2. 이제이 사람이 멀리 갈 수, 이건 갈 수 있습니다.
그럼 이제 8 살 문제는 크기 (4) 지금 크기가 2이었다.
우리는 아주 가까이 접근하고 있습니다. 다시 말하지만,이 두 요소의 가운데로 이동합니다.
>> 좋아요. 그럼 우리가 내려 라운딩이기 때문에 지금 우리가 항상 떠 가고 있다는 것을 종류의 불운입니다.
지금 우리가 7 우릴 떠나, 거리에 있으며 다른 모든이를 포기하기 때문에하지만 그건 괜찮아요.
가 박수를 쳐. 우리는 다시 7 발견했다. [박수] 좋아. 그래.
단지 1 개 초 기다려.
의 다음 프로세스 종류의 우리가 그러 생각보다 조금 더 걸렸습니다, 비록
솔직히, 당신의 첫번째 본능은 바로, 최고였다? 우리는 즉시 7 발견했다.
그러나 우리는 빠르고 이것 대에 상관없이이 예에서 무엇을 7를 발견하지 않았을
번호가 모두 정렬하는 경우 때문에 많은 전화 번호부의 페이지처럼
당신은 실제로 다시하고 다시하고 다시 문제의 절반을 버려야 할 수 있습니다.
그리고 이건 그냥 8 자리 숫자로이를 볼 수 매우 쉬운 일이 아닙니다
등 정말 시각적으로 볼 1000 페이지 전화 번호부에 반대,
하지만 여기이 경우에는 숀, 7 검색 한 경우
얼마나 많은 최악의 경우의 단계가 그를 데리고까요? >> [학생] 7.
최악의 경우 7. 음, 최악의 경우하지 7 8 문이 여기있을 경우 인치
그것은 그에게 8 단계를 취 것이다.
>> 그래서의 N 문 경우, 몇 년 전에 N 단계를 션을 촬영했을 수 있습니다.
자, 그렇다면,이 숫자가 정렬되는 알렉스, 주어진 -
우리는 우리가이 이야기에서 지금까지했던 곳에서 추론이 종류의 수 -
알렉스의 더 지능 알고리즘의 실행 시간이 뭐야
중간부터 시작하고 반복?
[학생] 3. >> 그래서 당신은 2 1로 8-4에서 이동하는 경우, 약 3거야.
3 단계 그래서 나보다 일반적으로, 그 로그 N 다시입니다.
당신은 이등분하고 반턱과 반턱과 반턱 할 때마다,
그 로그 n의이 아이디어의 표현입니다.
그리고 그렇게 단지 당신 3 단계를 취했습니다 것이며, 실제로는 한
일단 우리는 문을 이등분하고 반턱 오픈
이 숀에게 7-8 조치를 취 것이다 반면.
그래서 우리와 함께 올해 주셔서 감사합니다. >> 감사합니다. 회의를 웠어요.
알렉스에게 감사합니다. >> 저도 요. [박수]
>> 어떻게 다음이의 실제 의미 야?
지금은 솔직히, 우리 모두가 뭔가를 찾을 수있을, 8 문, 아닌 건 상상
단지 종이 조각을 찢어 우리의 본능에 이동하여 너무 빨리 뒤로 8 문.
그러나 만 문을 어떻게됩니까? 그런 일이 4,000,000,000 문 있다면 요?
4000000000 문의 경우에, 당신은 정말로, 알렉스의 알고리즘에 가고 싶어 할거야
우리가 전화를 시작하거나 더 일반적으로, 나눠서 맡을 것 같은 이진 검색,
당신은이 문제를 이등분하고 반턱 보관,
당신은 4,000,000,000 문이있는 경우, 몇 번이 반으로 40 억 자르다 수 있기 때문에?
[학생] 32. >> 실제로 32입니다. 당신은 종이 또는 머리에이 운동을하실 수 있습니다.
당신은 250 만 점, 점, 명확히 설명하는 데, 4 billion to 2000000000-1000000000 억으로 이동합니다.
당신이 수학을하면, 당신은 실제로 32받을거야
우리가 보통 2의 거듭 제곱으로 계산하기 때문에 그 사실은 컴퓨터 과학에 관한 것이다.
2 32는 4000000000로 발생합니다.
따라서 컴퓨터 과학 2의 거듭 제곱 이러한 종류의 관련성이 많이있어.
>> 그런데 억 8? 8000000000 문이있을 경우 몇 단계 그건 걸릴까요?
[학생] 33. 따라서 33 >>. 무엇 16000000000 문이 있다면? 얼마나 많은 단계 그건 걸릴까요?
[학생] 34. >> 34. 우리는 가지이 광고 nauseam을 계속 수 있습니다. 하지만 강력한 것입니다.
귀하의 문제에 더 많은 입력 수십억을 소개하지만, 아니 큰 일, 수
당신은 단지 1 추가 한입 아웃을하기 때문에 우리에게 이진 검색과 같은 일을 할 수 있습니다
이상 일반적으로, 나눠서 맡을.
하지만, 여기서 바람을 피우고있는 것 같아요?
알렉스의 알고리즘의 경우, 그녀는 숀 이상의 이득도 있었다.
그녀는이 숫자가 정렬 된 것을 알고 있지만, 알렉스는 그들에게 자신을 정렬 할 필요가 없습니다 않았다.
사전에 잘 만든의 칠판과 종류까지왔다
전 정렬 순서로 모두를 그린 다음, 나는 종이를 덮었다.
그러나 저를 얼마나 일을 가져 갔어?
우리는 임의 순서로 숫자와 도망을 시작했다면 -
이 경우에 이러한 간단한 숫자, 여기 8 1 -
우리는 이러한 값을 정렬 어떻게해야할까요?
이 임무를 맡은 사람이라면, 직관적 인 접근 방법 어떤 종류의 당신은 걸릴거야
숫자를 왕창 정렬에?
이러한 것들이 퍼즐 조각으로 배치되었다. 그래.
>> [학생] 내가 각 번호를 가지고 각 비교 것
왼쪽으로 계속. >> 그래, 좋아.
그래서, 옆의 비교, 각 번호를
그리고 당신이가는대​​로 물건을 rejiggering 목록, 친절을 따라 전진.
그래서 여기에 우리가 참여 더 어쩌면 몇 사람들의 기회가 있습니다.
우리는 와서 싶지만 8 더 많은 자원 봉사자가 있습니까?
귀하 이후 약간 덜 압력이 있던 건 아니다. 1, 2, 3, 4, 5, 6, 7, 8.
이리 오게. 너희들은 8을 통해 숫자 1이 될거야.
만약 우리가 사전에 짓 같은 방법으로 많은 알렉스이 정렬 작업을 수행 할 수없는 경우 봅시다.
1, 2, 3, 4.
계속하고 싶다면, 여기에 음악 스탠드와 나 사이의 무대에 정렬
화면의 슬라이드와 같은 순서를 유지해야합니다.
어 - 어.
우리는 다음 예 여러분을 도와 드리겠습니다. 아, 잠깐만, 잠깐만. 여기 우리는 간다. 기다립니다.
다음 예제는 지금입니다. 여기. 번호 8. 어서 올라 와요.
괜찮아요. 정렬이에 따라 붙들어.
음악의 측면에 조금 밀어은 여기 서 계세요.
그래서 우리는 4, 2, 6을 가지고 - 거기, 여기에, 거기에 요 - 3.
그래. 좋아요. 당신은 여기 이동합니다. 아니, 당신은 거기에있어.
그래, 바로 거기. 아니 잘못입니다. 바로 거기. 좋아요, 아주 좋아요. 좋아요.
그래서 지금의이 증가 순서로 정렬 보자.
>> 어떻게 이런 짓을에 대해 갈 수 있을까요?
좀 전에 제안 된 알고리즘은 왜 우리가 비교 그렇지 않아
그런 다음 서로 옆에 가지이며, 사람들이 어떤 실수를 수정
왼쪽에서 오른쪽으로 이동.
그래서 여기에 우리가 분명히 아웃 ​​순서, 4, 2가 있습니다. 의 당신을 교환 보자. 좋아요.
그래서 지금 내가 선을 아래로 이동거야. 4 번과 6 번, 아뇨. [웃음]
6 8, 정말 좋은. 8 1, 나에게 사람들을 교환 보자. 괜찮아요.
8 세 그래서, 당신들을 교환.
8 7, 나에게 사람들을 교환 보자. 5 뛰어난 8.
내가 정렬 목록을 제공합니다.
괜찮아요. 그래서별로 요.
하지만 더 좋아하기 때문에 더 큰 숫자 - 사례 지점 8 -
가지의 오른쪽에있는 왼쪽에서 이상 떠오르 있습니다.
그래서 바로 그 1도,하지만 그건 정말 문제가 해결되지 않아서 인 것 같아요.
>> 당신은 우리가 다음에 어떻게 그럼 무엇을 제안까요? >> [학생] 그러는하세요. >> 우리가 일을 계속.
그리고 다시 실현, 우리는 모든 인간을함으로써 일을 설정
종류의 지능적 그 사진을 바탕으로 자신을 준비하는 것은
지금 우리는 훨씬 더 체계적으로해야합니다.
우리는 코드를 작성하는 것처럼에 대한 알고리즘 있어야 -
이 경우 구두 의사 인치
그럼 내가 그 다시 시도해 보자. 꽤 잘했습니다. 그것은를 해결할 수 없습니다.
하지만 의심되면, 그냥 해하고 다시 시도하십시오. 그런데 2, 4, 더 이상 도움이되지 않았다.
4 6. 아! 약간 더 나은 지금 6과 1.
6 좋은 3. 6, 7, 7, 5, 7, 8, 좋아.
그는 목록의 끝 부분에 있기 때문 그리고 당신이 알다시피, 난 아마 8 무시할 수 있습니다.
우리가 누군가가 그의 옆을지나 갈 걱정을 할 필요가 없습니다.
하지만 그게 안전한 가정 있는지 보자.
지금 목록입니다 - 젠장 - 정렬 없습니다. 가 다시 해 보자.
2 자, 4, 4, 1, 4, 3.
4 번과 6 번, 좋아. 6 5, 좋아요.
6, 7, 8, 좋아. 그러나 통지, 내가 지금 여기에 중단하고 지금 중지 할 수 있습니까?
[학생] 예. >> 응?
당신 중 하나가 저 멀리 9 번이었다 있다면 요?
이 정렬 된 것입니다. >> 좋아. 이들이 처음에는 정렬 된 것입니다.
좋아. 그러니 다시 가자. 거의 다 왔어.
1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8.
>> , 지금은 완료합니다하지만 또 다시, 난 단지 내가 할 말한 건 할 수있는 컴퓨터입니다
내 유일한 기억은 지금은 실제로 작품의 비트 짓을한다는 것입니다.
여기서 뭔가 바뀌 었습니다.
그래서 기술적으로 시각 또는 알고리즘이 목록은 실제로 정렬되어 확인되지 않았습니다.
그냥 좋은 측정을 위해 그래서, 그냥이에 대한 항문을 위해이 1 시간을 더 해보자 구.
1 자, 2, 2, 3, 3, 4. 그리고 당신은 알아요?
그냥 좋은 측정을 위해, 나는 내 손에이 시간을 추적 할 거예요
내가 일을 얼마나 알아 둬 있도록 만들어 얼마나 많은 스왑 사실은 제가 했어요.
3, 4, 4, 5, 5, 6, 6, 7, 7, 8. 어떤 스왑 없습니다.
그래서 지금은 합법적으로 다시이 작업을 수행 할 수있는 바보 같은 것
때문에 나는 인간이 패스를 통해 작품 아무런 짓도하면
그들 중 아무도 종류 무작위로없는 경우 다음과 명확하게 다시 똑같은 일이
adversarially 자신을 주변에 이동. 그래서 지금은 중지 할 수 있습니다.
지금의이 질문을 물어 보자,이 사실을 얼마나 많은 일을 했어요?
그 얼마나 많은 조치를 취할거야? >> N 제곱.
그래, N 제곱. 당신은 어디로에서 제곱 얻을 N합니까?
당신은 각각의 NUM을 확인해야 -
이 N 번호가 있으며, 당신이 다른 N 번호와 각 번호를 확인해야합니다.
좋아. >> 그래서 그것은 제곱 보군. >> 좋아.
>> 그래서 아주 잘 맞아, 제곱 N 수 것 같지?
8이 경우에는 특히,이 사람들의이 보군,
하지만이 목록을 겪었 때마다 나는 두 번째에 대한 최초의 사람을 비교 한
다시 다시 다시 세 번째에 대한 두 번째와
내가 마지막에 도착했을 때, 나는 무슨 짓을 한거야? 난 redid.
우리가이 설명을 일반화하는 경우 그래서, 우리는 우리가 사람들에게 습니했습니다
그리고 난 분명, 8 단계 N 단계,이 알고리즘을 통해 갈 때마다 만드는 중이에요.
그러나 얼마나 많은 최악의 경우 시간이 나는 사람들이 목록을 통과해야합니까?
[학생] N 번. >> 아마 N, 오른쪽, 때문에 최악의 경우에
무엇은 아마도 첫인상에서 이러한 사람들의 최악의 경우 배치거야?
그들은 완전히 순서를 반대로하는 경우
때문에 그냥 정신 let's을 가정 - 당신의 이름은 무엇입니까? >> 브라운이에요.
보웬. 좋아요. 그냥 잠시 동안 여기에 온 보웬,.
>> , 보웬은 알고리즘의 시작 부분에서 여기 있다고 가정
우리는이 알고리즘에 따라, 여기 모든 사람들이 알고 있지만, 보웬하지 않습니다 -
당신이 저와 함께 산책을하고 싶다면 - 그는 주변의 처음처럼, 풍선까지가는되며,
끝으로 모든 방법입니다.
그러나 보웬 옆에있는 사람이 7 번이라고 가정 해 보겠습니다.
난 다시 가서 내가 다시 여기 길을 가야 의미 숫자 7을 얻을 수 있습니다.
지금은 번호 7 사람과 같은 산책을 가지고 있어야합니다.
그러나 번호 6가 그 옆에 있었고 다음 면요?
그럼 내가 가서 6를 얻을 수 있습니다.
그럼 다시,이 루프의 모든 반복에 나는 N 사람들의 각 얘기
그리고 내가 찾고 있어요 있는지 확인하려면 다음과 산책의 N을해야 할 수도 있습니다
다시 다시 다시 목록의 맨 끝에 가장 큰 요소의 모든.
따라서 N 일 n 번은 n 번 N 또는 n 제곱입니다.
>> 그래서 여기 이미 우리는 더 이상 로그 N없는 더 이상없는 알고리즘 n을,이
우리가 전에했던 것보다 실제로 더 있습니다.
따라서의 알렉스 종류, 난 일을 그녀에게 분명히까지 앞의 모든 짓을한다는 점에서 운이 좋았죠
그녀가 이진 검색 알고리즘에 즐길 수 있도록 고가의 작업의 모든,
n의 로그하는 것입니다.
그러나 월요일의 주제와 일치 수 있습니다.
우리는 우리의 실행 시간을 단축하기 위해 더 많은 비트를 사용, 조금 더 공간을 주었다.
많은 시간과 공간 간의 트레이드 오프가 같은
시간이 갈 일 준비의 앞에 정렬을 보냈다 사이에 역시 무역 오프가있을 수 있습니다
실제로 검색과 같은 알고리즘을 실행. 의 다른 하나를 시도해 보자.
너희가 빨리 재 배열 상관하지 않을 경우 스스로는 다시 한번 일치하는
별로 간단하게는 어디 약간 다른 무언가를 시도 두자
슈퍼 직관적있는 모든 pairwise 실수를, 그냥 수정으로.
의 대신 조금 더 천천히이 짓을 보자.
너무 제가 제안 것 하나는 아마도 매우 직관적입니다.
>> 또 한번, 또 한번 목록에서 가장 작은 사람을 선택하자. 그래서 여기에 우리가 이동합니다.
네, 당신은 내가 이렇게까지 ​​본 가장 작은 사람입니다
그래서 정신적으로 단지 지금 당신줌으로써 그 기억거야.
2. 와우! 4 번 잊어 버려요. 난 그냥이 목록의 새로운 작은 요소를 발견했습니다.
나는 어떤 종류의 기억이에 갈거야. 6, 8.
와우! 1. 안녕히 가세요. 그래서 지금은 숫자 1을 기억하는거야.
우리는 1 작은 것을 알아,하지만 난 컴퓨터입니다. 어떤 0이 있다면 요?
어떤 -1이 있다면? 나는 계속해야합니다.
따라서 3, 7, 5, 아뇨. 좋아요. 그래서 숫자 1은 가장 작은이었습니다.
제가 목록에서를 선택하자 - 꼭이 길을 갈 -
와 목록의 시작 부분에서 임의로을 넣어.
자, 기다려 봐. 사기에 드는데.
이 남자들은 8 명 목록 만 배열을 나타냅니다 경우
연속 메모리 8 덩어리가 - 당신은 한 순간을 위해 다시 스테핑 줄래?
바로 여기 공간은 실제로 없습니다.
그럼 우리는 공간을 어떻게해야합니까 - 이름이 뭐야? >> 새미. >> 새미.
우리가 어떻게 새미를위한 공간을 어떻게해야합니까?
>> 우리는 내 앞에있는 N 이동합니다. 좋아요 >>.
그래서 우리는 그 전에있는 N 사람들을 움직일 수
너희들이 왼쪽으로 한 고의적, 극적인 조치를 취할하고 싶다면.
, 그들은 모두 한마음으로 그 짓을하지만, 지난번에 내가 몇 가지 코드를 작성
여러분 모두 한 번에 많은 물건을 움직일 분류 할 수 없습니다.
우리는 한 번에 한 번 모두를 이동, 루프에서 할 수 있습니다.
너희들이, 오른쪽으로 돌아 가야할 거 신경 안 써요면
그리고, 새미의 여지가 아직 없습니다 때문에 물러 할 수 있다면,
지금 한번 해보자 구. 어디 새미 순간 전 이었어요? 바로 거기.
그래서 차이가 있습니다. 그럼 당신은 새미의 장소로 이동 수 있습니다.
지금 옆에있는 사람까지 지금 현재 다음 사람, 다음 사람. 이제 우리는 새미을위한 공간을 갖추고 있습니다.
관객에서 이제 사람 - 잘 했어, 정확 했지
그 느낌이 시간이 많이 걸리는 약간 - 어떤 빠른 게있어? 그래.
[학생] 새로운 배열? >> 무슨 뜻이지? >> [학생] 새로운 배열? >> 그래, 좋아.
>> 단지 무역 오프의 테마가 너무 일관성, 왜 난 그냥 새로운 배열을 만들지 마
그리고 새미 예를 들어,이 사람들의 앞에 공간에서 수영됩니다
그리고 우리는 모두 새로운 배열을 작성하실 수 있습니다. 너무 일 것입니다.
하지만 오늘은 더 많은 공간을 소비에 관심 없어. 또 다른 방법은 무엇입니까?
[학생] 스왑. 좋아요 >>. 우리는이 두 녀석을 교환 수 있습니다. 이름이 무엇입니까?
마리오. >> 마리오. 마리오 그래서 현재 여기에 있었다.
새미, 당신은 잠시 동안 백업 할 수 있습니다? 마리오가 여기 있었어요.
당신이 새미가 어디가는 거 신경 안 써요 만약 그렇다면 우리는 더 이상 당신을위한 공간이 없어요
우리는 깨 놓을 게요, 지금은 새미의 교환 작업이 훨씬 더 빨리이라고 주장 할.
우리는이 사람들을 교환하거나, 어쩌면이 녀석을 교환 한 작업을 한
하지만 우리는 더 나은 느낌 그 때문에, 1, 2, 3, 4 안 했어요. 자, 기다려 봐.
4 번이 처음에 가까운 가지했기 때문에 나는 가지 문제가 악화했다.
지금 4 번이 마지막에 좀 더 가까이하지만, 난 정말 알고 또는 그것에 대해 관심이 없었어요.
그래서이 4 번이 좀 멀리의 운명 곳에서입니다 단지 운이 나빴군요.
따라서이 알고리즘을 반복 지금 까.
>> 오래 그 이야기를했는데, 요점을 되풀이하기 위해, 우리 모두가 목록을 걸어 었어요
가장 작은 번호가 사람을 찾고 있어요.
이제 다시 한번 해보자 구. 우리는 더 이상 새미에 대해 걱정할 필요가 없습니다.
우리는 여기에서 할 수 있습니다. 와우! 번호 2. 아주 적은 수의 기록이다.
6, 8, 4, 3, 7, 5. 그래, 좋아.
그리고 다행히, 우연의 일치에 의해 움직일 필요가 없습니다 - >> 윌리 있습니다.
윌리 그는 지금 자신의 올바른 위치에 때문입니다.
다시이 작업을 수행하자 이러한 두 녀석을 무시합니다.
6. 아주 적은 수의 기록이다. 와우! 8 확실히 큽니다.
4. 의 4에 초점을 보자. 와우! 3 더 있습니다.
7 5. 그럼 우리가 이제 어떻게하지 - >> 로저. >> 로저?
의 번호는 6 그를 교체 보자.
따라서 6 3 교환하고 싶은 경우
우리는 이제 가지, 그녀가 있어야 할 자리에 가까운입니다 6 운이 생겼는지
하지만 여기 우연의 일치입니다. 그럼 지금 여기 가자.
8 매우 작은 숫자입니다. 와우! 4 작습니다.
6, 7, 5. 우리는 지금 무엇을해야합니까? >>의 스왑. 정확히 >>.
이제 빠르게 이러한 종류의 한번 해보자 구.
8, 6, 7, 5. 5 어디가는 거지? 좋아. 좋아요.
6, 7, 8. 6 그녀가 어디 있어야됩니다. 이름이 무엇입니까? >> 로잘리.
로잘리 그녀가 어디 있어야됩니다. 7에 도착 - 봅시다. 7, 8. 좋아요.
그럼 7 그녀가 어디 있어야됩니다. 이름이 무엇입니까? >> Amna. >> Amna.
>> 그럼 Amna는 그녀가 어디 남아 도착, 그는 지금 있어야 할 곳에 숫자 8은 이미 있습니다.
그래, 좋아. 우리가 있지만, 여기에 자신에 대한 작품을 만드는 것 같아요.
어떤 궁극적으로이 알고리즘의 실행 시간있어?
우리가 아니라, 8과 같은하지만, N 이러한 사람들에 대해 생각한다면? >>은 N입니다.
이 단계를 보군,하지만 우리는 매일 시간을 확인하고 있습니다.
좋아요. N하지만 매번를 확인 건가요?
이 단계를 보군 경우 좋아,하지만, 난 그냥 1, 2, 3, 4로 이동하여 귀하를 정렬 할 수 없었을해야합니까?
오! 그래요, 그게 큰 차이입니다.
따라서 n은 왜 제곱? 정말 무슨 일이에요?
이 목록의 N 사람들이지만, 목록에서 가장 작은 사람을 찾을 수
최악의 경우 몇 단계 나 데려 가야 해요? >> N.
>> N, 오른쪽, 최악의 경우, 숫자 1, 저기 모든 방법이기 때문에
그래서 그 사람을 얻거나 그녀 가야 해요.
그리고 드디어 1 작은 였지만 때, 죽음이 그들을 교환 꽤 빠르입니다.
하지만 지금은 처음부터 시작하여 사람을 찾아 있습니까?
2 다음 작은 사람. 최악의 경우에 2 어디있는거야?
오, 맙소사. 이 말에 여기까지입니다.
그래서 지금은 다른 N 단계, 다른 N 단계를 완료했습니다.
그리고 우리는 N 사람들을 보유하고 있으며 최악의 경우에 가장 작은 사람이 거리에 N 단계 인 경우,
다시는 n 번 N이고, 그래서 우리는 다시 제곱 습니했습니다.
이건 너무 기분이 좋다되지 않습니다.
그리고 사실, 심지어 가장 경우에 - 소위 정렬 시작하는 가정 -
내가이 N 사람들을 정렬하려면이 알고리즘을 사용하기 위해 얼마나 많은 단계를 수행합니까?
N은 제곱. >> 나도 들었어 N 제곱. n은 제곱 이유는 무엇입니까?
당신은 여전히​​ 매번 확인해야합니다 때문입니다. >> 그래.
그리고 당신이 그들을 교체해야합니다. 우리 인간은 신이의 종류 >>하더라도
의미에서 시각적으로 우리가이이 정렬되는 것을 볼, 그냥 할 수있을
컴퓨터는 스마트하지 않습니다.
그것은, 여기, 그리고 여기와 여기 보는거야
하지만이 찾고있어하는 가장 작은 요소입니다 경우,
당신은 단지 무슨 점으로 가장 작은 요소를 발견 한 거 알아요? 일단 당신이 마지막에와 있습니다.
그러나 그 시점에서 당신은 단지 현재 가장 작은 요소를 발견했습니다.
당신은 반드시 세상의 상태에 대한 다른 아무것도 몰라요.
그럼 당신은 다시 다시 다시 가야 해.
>> 난 괜찮을 2를 선택하기 때문에 정말로이 시간이 바보 그래서, 당신은 가장 작은이야
하지만 아직 총을 압니다하지 않습니다.
3, 4, 5, 6, 7, 8. 그래, 좋아. 2 실제로 작은이었습니다.
지금의이 다음 작은를 찾으실 수 있습니다. 좋아요.
3, 현재 가장 작은이야. 어디 봅시다. 4, 5, 6, 7, 8. 좋아, 다시 운이 좋군.
3 오른쪽 장소에 실제로이었다. 하지만 다시이 일을 다시하고 다시 유지거야.
우리가 어떻게 아무리 약간 더 할 수 있습니까?
대신에 pairwise 작은에서 큰 사람들에게 풍선을 갖는
대신 다음 작은 사람을 선택 목록을 앞뒤로가는,
왜 우리가 대신 단계하여 새 목록 단계로이 사람들을 삽입하지 마십시오?
의이 일을 해 보자. 지금 내가이 일을 삽입 정렬이라고 불러.
그래서 여기에 우리가 여기에 있습니다. 번호 1. 이 목록에있는 다른 사람에 대해 신경 쓰지 않습니다.
내 목표는 지금 정렬 목록의 처음에 숫자 1을 넣어하는 것입니다.
제가 메모리 만 8 덩어리가 있기 때문에 그리고, 제안거야
임의로 지금은, 내 추측 정렬되지 않은 목록 사이의 벽이다
내가 주장하는거야 저 뒤에있는 사람이 정렬됩니다.
이제 우리는 숫자 1이 있습니다.
내 정렬 목록에 그를 삽입 할, 난 그냥 여기에 벽을 이동로 갈 거에요
지금 내가이 목록이 정렬됩니다 주장이 목록은 정렬되지 않은 수 있습니다 - 적어도 지금까지 내가 아는 한.
한 번에 모든 숫자를 볼 수 없습니다.
>> 지금은 숫자 2가 발생하기 때문입니다. 그와 함께 무엇을해야합니까?
나는 정렬 목록에 당신을 삽입합니다. 하지만 그게 얼마나 쉽게 확인합니다.
난 그냥 볼 수 있습니다. 숫자 1이 있습니다. 아, 분명 2 숫자 1의 측면으로 이동합니다.
지금은 3 어떻게해야 하죠? 나는 정렬 목록에 귀하를 삽입합니다. 하지만 그건 아주 쉽게했다.
이 쉬운 슈퍼입니다이 아주 쉽게, 이쪽은 아주 쉽게, 아주 쉽게, 아주 쉽게합니다.
그리고 이제 모든 것을 내 뒤에 정렬하고 있으며, 그 얼마나 많은 조치를 취할거야?
[학생] N. >> 따라서 만 보군. 우린 운이 좋아.
단지 N 이유 였죠? >> [학생] 목록이 정렬되었습니다 때문입니다.
이 목록은 이미 정렬됩니다. 그래서 우리는 운이 좋았 군.
그러나 우리는, 알고리즘 행운의 종류를 이용합니다이 시간을 설계
불필요한 시간을 낭비하지 않는 방법으로에 가장의 경우.
그래서 우리는 지금 우리는 거품 정렬을 뭐라고 할 수 있습니다
어디에서 pairwise까지 거품의 사람들 이란다.
우리가 다시 다시 작은 사람을 뽑아 낸 곳 우리는 지금 선택 정렬되어 있습니다.
그들이있을 곳은 우리가 어떤 종류의 사전 명을 넣는 이제 지금은 우리가 삽입 정렬을
점점 정렬 명단에 없어요.
우리가 할 수 있다면, 여기 애들에게 박수. [박수]
의은 우리가 5 분 쉬었다합시다.
그리고 우리가 돌​​아 왔을 때, 우리는 물 밖으로 이러한 알고리즘을 모두 버릴거야
더 나은 뭔가를. 괜찮아요. 정말 감사합니다. 당신은 기념품으로 사람들을 유지할 수 있습니다.
괜찮아요. 우리가 다시 있습니다.
>> 그리고 정말 빨리 요점을 되풀이하기 위해, 정렬 이러한 3 가지 방법을 가지고
전체 점은 지점에 도착 곳 알렉스 같은 사람
숀 할수 같은 사람보다 더 빨리 숫자의 목록을 검색 할 수 있습니다.
그리고 우리는 8 자리 숫자와 같은 간단한 예제를 가지고하더라도,
당신은 쉽게 8 웹 페이지, 8000000000 웹 페이지를 추정 할 수
페이스 북이나 800,000,000 친구.
따라서 이러한 알고리즘은 확실히 값을 그 종류의 확장 할 수
그리고 아이디어는 궁극적으로 동일합니다.
따라서 버블 정렬은 우리가 가지 가장 큰 사람을 부풀어 오른 곳 처음
pairwise 사람들을 교환하여 오른쪽에있는 모든 방법입니다.
그럼 우리가 어디 좀 더 의도적으로 우리가 선택 정렬을 뭐라고했다
다시, 목록을보고 또 한번, 또 한번 가장 작은 번호를 선택하고 계속
의 논리적 결과 목록이 결국 정렬되어 있습니다.
그런 다음 세 번째는, 내가, 적합한 장소로 사람들을 삽입
우리는 목록이 이미 정렬 된 것을 매우 인위적인 예를 했어,
하지만 그 메시지를 보낼이었다 삽입 정렬의 경우에
당신은 행운을 가질 수 있습니다.
숫자가 이미 정렬되어 경우에만 많이 확인하는 N 조치를 취할 겁니다
선택 정렬 반면 당신은 좀 더 터널 비전이야
그리고 당신은 목록이 이미 정렬 않는다는 것을 깨닫게하지 않습니다.
그래서 여기 활동에 거품 정렬을 살펴 보자.
다음 예제에서, 우리는 수직 막대를 볼 것입니다
우리가 시각화 일을 정렬의 정렬 할 수 있도록 그의 높은 숫자를 나타냅니다.
작은 바, 숫자 작은, 큰 바, 더 큰 수를 표시합니다.
>> 그리고 우리는이 기본 속도에서 재생됩니다.
그것은 지금 조금 빨리 이동하는거야,하지만 빨간색은 2 개의 바 보여줄 수있어
나란히 비교된다.
당신이 자세히 볼한다면, 어떤 일이 생기 것은 그 바의 순서, 경우
하나 작은은 왼쪽으로 오른쪽으로 더 큰 하나를 이동됩니다
그리고 당신은 발전 유지.
우리가 다시 다시이 작업을 수행다면,주의 그 작은 바
왼쪽의 길을 인칭 둘 건가요
그리고 가장 큰 막대는 오른쪽으로 길을 인칭 유지하려고합니다.
그리고 실제로, 우리는 패턴을 오른쪽에있는 모든 방법을보기 시작하고
처럼 우리는 8 본 후 7 결국 인간 목록의 맨 끝 부분에 품어.
그래서이 매우 빠르게 조금 지루한 얻을 것입니다, 그러니 내가 잠시 동안이 일을 막아야 해.
나를 훨씬 더 빨리 될 속도를 변경 보자.
제가 알고리즘을 바꾸지는 않을 겁니다, 그냥 애니메이션이 빠르게 일어날 만드는 중이에요.
아직도 거품 정렬, 동일 알고리즘
지금 당신은 우리의 언어 데모보다 훨씬 빠르게 볼 수 있습니다
하는 가장 큰 요소는 실제로 정상에 품어 있습니다.
>> 옆으로,이 작은 하단 왼쪽에 사각형과 하단 바로
당신이하고있는 얼마나 많은 비교를 같은 단지 약간의 알림입니다.
하지만 지금은 모양을 이루고있는 피라미드에 집중할 수 있으며, 거기에 간다.
가장 작은 요소는 왼쪽, 오른쪽에있는 큰, 그리고 다른 사이에 모든에 있습니다.
지금의 대신 선택 정렬을 살펴 보자.
나는 가서 정지를 누르거야. 우리는 바의 새로운 임의의 집합을받을거야.
선택 정렬, 리콜, 다시 다시 다시 목록을갑니다
가장 작은 요소를 뜯어. 그래서 여기 선택 정렬입니다.
우리가 pairwise 비교하지 않았기 때문에 지금은 상황이의 더 적은 일 것 같습니다
하지만 우리는 오른쪽에서 왼쪽으로 작은 요소를 체리 따기의 정렬하고 있습니다.
그건 거의 시간이 걸렸습니다, 이분법 이미 혼자 야.
알고리즘은 버블 정렬과 같은 N 제곱 시간이 걸릴이라고합니다해서
및 선택 정렬처럼, 그건 최악의 경우 실행 시간은 정말 있습니다.
예를 들어,의 경우,,, 말의 선택 정렬하게
사실은 가장 작은 사람을 선택하고 있고, 여기 그 사람 그녀를 넣어
그럼 다시하고 있어요, 그럼, 또 이러 네
하지만 할 수있는 약간의 최적화가 발생했습니다.
>> 이 경우 새미 - 나 숫자 여기에 1을 이동 자마자 -
난 이후 그와 함께 어떻게해야 했어? >> [학생] 그 둡니다.
자, 그를 떠나? 아무것도.
제가 가장 작은 요소를 선택한 경우 때문에 다시 본 새미 이야기 할 필요 없어
여기 바꿔, 왜 시간 낭비 내 전체 목록의 끝으로가는거야?
다음 반복에서 내 실제 만 3 번, 2 번 만 이동하세요.
그래서 현실에서, 나는 N 일 n 번 짓도 안했습니다.
1 일, 다음에 n - - 2 일, 다음에 n - 3 일, 나는 다음에 n 일, n을 짓
다음에 n - 4, 점, 점, 점입니다.
우리는 의미 기하학적 시리즈의 조금 있습니다
당신은 점점 더 작은 숫자를 추가하고 있습니다.
안 N + N + N + N 있지만, N + 7 + 6 + 5 + 4 + 3 + 2 + 1.
그리고 일반적으로 무엇을 작동합니다 -
난 그냥 잠시 여기 내 보드 망치지에 갈거야 -
/ 2 - 그 N과 같이 (1 N)으로 운동을거야
당신은 모든 치트 시트가 수학 책의 뒷면 모습의 경우 우리가 어떤
수식하십시오.
당신이 뭔가를 추가하는 경우 n은 + N - 1 + N - 2, 그건이 같은 것으로 밝혀 작동합니다.
의 우리는 그냥 종류가이 문제를 곱하면, 우리가 2 제곱 마이너스 N / N있어.
그래도, 난 말을 N 제곱 보관, 나는 정신 바로 가기를 복용 종류 있었기 때문 이네
현실에서, N 마이너스 제곱 N 2로 나누어은 참으로 단계의 진정한 수 있기 때문에
우리가 정말 일어나 계산하는 경우 선택 정렬과 같은 알고리즘이 소요될 것으로
이러한 비교의 우리가 뭘하고 있었 좀 바쁜 일 모두.
그러나 솔직히, n은 도대체 관심 만 또는 억처럼하게
당신은 2로 나누어 억 제곱 마이너스 억을하고 있다면 요?
제곱 억은 큰 숫자입니다.
당신은과 다른 억원에서 걸릴 수 있습니다 - n을. 정말 큰 문제가 아니에요.
그래서 더 큰 숫자가 가서 덜 중요한이 낮은 명령 조건이 있습니다.
이 단계의 번호 quadrillions에 대해 얘기하고 경우 2로 나누어 무슨 상관이 있어요?
>> 따라서 일반적으로, 컴퓨터 과학자, 그래도 가장 큰 용어를 던져하는 경향이
우리는, 그냥 세계를 단순화하고 그런 말을 그 알고리즘
약 N 제곱 단계를했다. 그 알고리즘의 실행 시간입니다.
그래서 우리는 몇 가지 구체적인 예와 함께 한 순간이 다시 올거야
하지만 지금은, 그 직관적 인 동기 부여의 종류는 우리의 세계를 단순화 배후
그리고 오히려 이러한 모든 멋진 수식에 들어가기보다 가장 중요한 조건에 대해 얘기.
그래서 그런 선택이었는데, 우리는 거기에 약간의 운이 좋군.
가 삽입 정렬 살펴 보도록하겠습니다. 내가 가서이 하나를뿐만 아니라 시작하자.
지금 무슨 일이 패턴을 발견하는 것은 약간 다릅니다
우리는, 임의의 숫자로 시작
하지만 우리가 실제로 최악의 경우에 단계의 수를 계산하면,
목록이 오른쪽 순서로 완전히 시작하는 경우
우리는 많은을 실현하기 위해 N 조치를 취할 것입니다.
>> 그러나 목록은 거꾸로 실제로 있다면 - 예를 들어, 여기이 경우에 -
우리가 실제로이 경우 더 많은 일을해야 할 다음 확인합니다.
이 하나가 더 힘들어 종류 인 것 그리고 가지 당신 생각해야
왼쪽에있는 작은 요소를, 우리는 운이 가지고 있기 때문에 그건합니다.
이 목록은 역에서 실수로 정렬되었습니다.
대조적으로, 삽입 정렬과 우리가 여기 우리 인간과 무슨 짓을 모방하는 경우
시작 정렬 사람들로 시작하고 그때까지, 바로, 아주 좋은 알고리즘거야?
이미 사실 정렬있어.
따라서 이것들은 우리에게 데려가는거야 정확히 얼마나 많은 시간을 요약 해 두자
실제로 훨씬 더 간단 단지 전문 용어의 비트 또는 표기법을 도입하여
의 fanciness 분류가 제안보다.
여기에있는 것이 큰 O가 화면에, 컴퓨터 과학자는 일반적으로 사용 무엇
알고리즘의 최악의 경우 실행 시간을 설명합니다.
>> 다시 말하지만, 최악의 경우에, 그것은 완전히 상황에 따라 달라입니다.
우리는 최악의 경우에 의해 무슨 뜻인지 전혀 우리가 얘기하고있는 그 문제에 따라 달라집니다.
그러나 정렬의 경우, 어떻게 최악의 시나리오?
그냥 우리에게 많은 일을 의미처럼 그 느낌 때문에 모든 것은 반대로 할 필요가있다.
나는 우리가 지금까지 본 적이있는 알고리즘의 몇을 메모 해 두었다했습니다 :
선형 검색, 전화 번호부 또는 종이 조각과 같은 바이너리 검색
그런 다음 버블 정렬, 선택 정렬 및 삽입 정렬처럼 우리는 우리의 인간으로 본
그리고 1 명의 결국 정렬을 병합이라고 할 겁니다.
따라서 최악의 경우 선형 검색에 얼마나 많은 단계가 숫자 7을 찾을 걸리나요
숀 얼굴과 같은 N 문이 있다면? >> [학생] N.
N. 그래서 우리는 n의 큰 O를 작성하는거야.
전 그냥 빈칸을 채워거야. 이건 그냥 빈 칸의 격자입니다.
그러나 선형 검색에 가장 좋은 경우에, 7, 목록의 맨 시작 됐을
숀은 목록의 시작을보고 시작했습니다 수 있습니다.
당신은 선형 검색을 사용하고 그냥 왼쪽에서 오른쪽으로 또는 왼쪽으로 어쩌면 바로 확인하고면 -
그들은 동등한 야 - 최고의 경우에 얼마나 많은 단계 수도 선형 검색
션의 알고리즘 같은 겠지? 단 1 단계.
>> 그래서 오메가 표기법 야 말거야.
이것은 단지 자본 오메가 있습니다.
오메가는 가장 사건이 시간을 실행 말하는 섹시한 방법입니다.
따라서 가장 좋은 경우에 실행 시간은 단일 단계 또는 상수 단계입니다 -
이 경우 1 -하지만 최악의 경우에, 큰 O, 실제로 N 단계입니다.
그리고 여기이 한 세타, 우리는 실제로 지금 보는 않을거야.
그것은이 특정 예제 관련이 없습니다.
하지만, 지금은 이진 검색을 해 봅시다.
이진 검색과 최악의 경우 몇 단계는 숫자 7을 찾을 걸릴 것입니다
또는 우리가 찾고있는 무엇이든? >> [학생] 로그 N.
아직도 알렉스 재수가있어처럼 있으므로 로그 n을 데려 갈
우리가 정말 methodically 문제를 통해 일할 때
그리고 그녀는 그녀를 바라 보았다 매우 마지막 문까지 7 번을 찾을 수 없습니다
하더라도, 공정성에 그녀는 길을 따라 특정 문을 던져 해
최악의 경우에는 이진 검색 로그 n의 실행 시간이 있습니다.
또, 이번 나누어과 정복을 말한다.
그런데 가장 좋은 경우는?
그녀가 무대에 왔을 때 알렉스는 실제로 오른쪽에 가장 사건을 경험했다.
그건 바이너리 검색에 얼마나 많은 조치를 취할거야? >> [학생] 1.
1 단지 그녀는 운이 좋았을 때문입니다.
오메가 가장의 경우 시나리오를 의미하기 때문에 그 사실은 괜찮아
그냥 무작위로 엄청난 행운이라도 최선의 경우 입력.
>> 자,이 역시 우리는 지금 휴가를 비워, 그냥가는거야.
버블 정렬하는 방법에 대해 지금은?
버블 정렬과 함께 최악의 경우, 모두, 역 순서입니다
그래서 우리는 버블 링을 많이해야 해요.
그러나 얼마나 많은 단계 최악의 경우에 데려 갈 것을? >> 제곱 [학생] N.
당신이 생각하는 경우 때문, N 제곱했습니다
목록이 완전히 거꾸로 인 경우 - 8 여기에있다, 1 여기있어 -
문제는 거품이 시작할 때, 숫자 8은, 이쪽을 이동하는 것이다
이런 식으로, 이런 식으로, 어디에은 최악의 경우에 7 번입니까?
여기 그녀가 저기 남아 있습니다. 그래서 우리는 다시하고 다시 수행해야합니다.
1 단계 다음에 n - - 2 단계 우리가 다음에 n 단계 N받을 곳 고.
그리고 당신은 내 말을하면 - 당신은 가지를, 나가 곱하면
그것은 약 우리가 지금 무시한다고 다른 조건을 결국 제곱 보군 -
다음 최악의 거품 정렬에 제곱 습니되어 있지만요.
그러나 버블 정렬과 최선의 경우는 어떤가요?
어떻게 가장의 경우입니까? 숫자의 모든 이미 정렬됩니다.
그리고 사용되는 경험적, 내가 사용하는 트릭, 무슨 일 일까
나는 더 일을 한 적이 없음, 따라서 초기에 막을 수 있다는 것을 깨닫게?
[학생]을 한 번 확인합니다. >> 한번 확인합니다. 하지만 길을 따라 대체 뭘 한 거지?
내가 만든 얼마나 많은 스왑을 추적하는 데되었습니다.
그리고 내 손가락에있는 모든 스왑을 계산하지 않은 경우, 그럼 더 일을 한 게 없어 깨달았습니다.
난 분명히 다시 더 작업을 수행하지해야하지 않아요, 그럼 난 그냥 중지 할 수 있습니다.
>> 따라서 버블 정렬의 가장 경우에 목록이 이미 정렬 된 경우,
당신은 최고 사건이 시간을 실행 오메가 표기법이 무엇을 말을하는거야?
이제 막 보군. 우리는 일을해야하지만, 우리는 작품의 한 거리의 가치를해야합니다.
그리고 여기에이 부분을 공백으로 남겨거야.
이제 선택 정렬.
선택 정렬 내가 다시 다시 작은 사람을 뜯어했다.
그리고 우리가 그였다의 실행 시간이 무슨 얘기를 했죠?
- 그게 N 최악의 경우 제곱.
그리고 불행하게도, 가장 경우에 또한 제곱 보군
이 세상의 신이보기의 정렬이 없기 때문에,
나는 내가 실제로 가장 작은 사람을 발견 한 전체 반복에 알아요.
정말 선택 정렬 종류, 그 의미에서 엿
하지만 거꾸로은 직관적는 거입니다.
당신이해야 할 모든 루프에 대한 중첩 된 몇를 작성 있기 때문에, 잘 코딩 아주 쉽게
일반적으로, 그 가장 작은 요소를 찾고지나
다음이 목록의 끝 부분에 속하는 가장 작은 요소를 넣습니다.
그래서 여기 너무 트레이드 오프가있을거야.
당신이 생각하고 실제로 코드를 작성하여 무언가를 개발하는 데 걸리는 시간의 양
당신은 알고리즘보다 빠르고 성능을 원하는 경우 잘 시간이 더 걸릴 수 있습니다.
>> 그러나 최대 코드 무언가 당신이 정말로 단지 종류의 경우 신속하고 더러운
불과 가지, 당신이 생각할 수있는 바보 가능한 아이디어를
코드에 몇 분 정도 걸릴 수 있습니다,하지만 큰 데이터 세트
당신의 알고리즘은 실행 시간이 걸릴 수 있습니다.
그리고 I 대학원 때때로 이러한 무역 오프를 만들 수있을거야.
그것은 오전 3시 것, 몇 매우 큰 데이터 세트를 분석하려고했던
제가하는 보안 연구에 관한, 그리고 중 5 분 지출되었다
조정 데이터를 분석하고 잠을 잘 나의 프로그램을
그 즉시 실행하고 다시 잠을 갈 수 있도록하거나 제대로 받고 8 시간 보내십시오.
그리고 거기에 너무 그것은 의식의 결정 이죠.
적은 개발 시간 더 잠을 자고있어.
돌이켜 보면, 아마 권장 안됩니다
여기에 목표는 코드 품질을 최적화 할 때하면
하지만 너무 현실 세계에서 매우 합리적인 트레이드 오프입니다.
적은 시간, 적은 성능이나 반대도 마찬가지입니다.
그래서 여기에 우리가 결국 세타에 대해 이야기 할 수있는 기회를 얻을.
세타 표기법은 컴퓨터 과학자 대화에서 가져 할 수있는 일입니다
큰 O와 오메가는 동일 일어날 때.
당신은 세타가 정말이 빡빡 행의 종류입니다 메시지를 보내 말한다.
시나리오 좋은 또는 나쁜 여부에 상관없이, 그것은 제곱 습니 없어요.
그래서 여기이 기사에 단지 관련 없습니다.
삽입 정렬은 우리가 바라 보았다 마지막입니다
어디 단지 적절한 장소에 모두 삽입되었습니다.
우리가 본 것을 본다면 가장 좋은 경우 어떻게 삽입 정렬의 실행 시간 였죠?
[학생] 최고의 사건? >> 가장 좋은 케이스.
>> 가장 좋은 경우에 모두 정렬 있기 때문에 그것은, N되었습니다
그리고 새미하고 다른 하나는 정말 전혀 이동했다.
그들은 바로 이곳에서 이미 있었다.
가장 좋은 경우에 따라서 삽입 정렬이 경우, N입니다.
그러나 최악의 경우는 제곱 N의 종류입니다. 이유는 무엇입니까?
인간의 내 목록에 역순 인 경우는,
처음 숫자 8을 시작하고 바로 여기에 올바른 위치에 그를 삽입하거나 그녀.
옆으로 이사어요. 이 사람들은 그 사람을 정렬되지 않은 있거나 그녀는 정렬됩니다.
하지만 지금은 누가 다음에 찾을 일이야? >> [학생] 7.
최악의 경우 7은 반대 순서로 잖아.
>> 그래서 여기 7입니다. 7 어디에 속해 있습니까? 물론 제 뒤에.
그러나 지금은 7 사실은, 바로 내 뒤에 만 8 번 뒤에하지 귀속
나는 "말 실례지만, 8 번해야하므로,이 방법을 이동합니다 수 있습니다
"7를위한 공간을 마련하기 위해?" 지금은 6 발생합니다.
"아,, 숫자 8 숫자 7 실례, 당신은 6 공간을 확보하기 위해 이동할 수?"
다시 말해, 삽입 정렬로, 나는 많은 운동을하고 안하더라도,
제 뒤에 사람들이 더 많은 일을하고 있으며, 사람이 시간을 비용있어 그.
이 컴퓨터 시간을 비용거야.
따라서 삽입 정렬의 경우 우리는 여전히 고통 받고 있습니다.
이 단계의 총 수를 추가 할 경우, 약 N 제곱 때리고 결국
이 사람들은 그 목록에 다시 삽입 할 인간을위한 공간을 확보해야합니다 때문입니다.
그리고이 경우에는 세타는 손에 특정 이야기에 적용되지 않습니다.
그거 좋네요 좋은 전부입니다. 우리는 실행 시간에 대해 얘기 중이 3 가지 다른 방법이 있습니다.
우리가 실제로 알고리즘을 코딩하려한다면이 실제 측면에서 무엇을 의미합니까?
>> 거기에 더 나은 알고리즘이 있다는 내가 제안하자
그거 자체는 몇 가지 무역 오프가 있습니다.
우리는 정렬 병합 전화를하고 있으며,이 마법의 알고리즘의 일종 이죠
그건 정말 빠르고 어떻게 든 작동, 그것은 적어도 의사에 표현하기 위해 너무 쉬운 일이야.
이 알고리즘 병합 정렬의 구현은 다음과 같이 될 것입니다.
정신 검사가 먼저 - 무엇이든 N 번호, N 사람들 - 당신은 N 요소를 제공 할 때.
n은 2보다 적은 경우, 정렬 방금 중지 병합합니다. 너무 말을 반환합니다.
n은 2보다 작다면 왜 멈출까요? >> [안 들리게 학생 응답]
맞아. 또, n은 목록의 번호입니다, n은리스트의 크기입니다.
n은 2보다 적은 경우 즉, 귀하의 목록 중 1 의미
이 1 번이라면 어디서 분명히 정렬하고
또는 정렬 할 수있는 게 없다고이 경우 0,,
그래서 우리는 기본 케이스의 종류가 필요합니다.
목록 상관 방금 없습니다 너무 짧은 경우, 문자 그대로 아무 짓도하지 않습니다. 돌아갑니다.
그렇지 않으면 요소의 왼쪽 절반을 정렬 한 다음, 요소의 오른쪽 절반을 정렬
그런 다음 2 정렬 절반을 병합합니다.
>> 내가 얼마나 요소를 정렬하는 방법을 부탁 해요된다 이런 종류의 작은 컨닝 것 같습니다
당신은 "오른쪽 절반을 정렬, 왼쪽 절반을 정렬합니다."말씀이신가요
난 대답 "좋아. 어떻게 왼쪽 절반을 정렬합니까?"
"완료 후, 왼쪽 반은 왼쪽 절반을 정렬 왼쪽 반은 오른쪽 절반을 정렬합니다."
당신은 주기적는 정렬의 의미 정의는거야
하지만이 경우 실제로 화려한 걸 밝혀졌다.
그것은 진정으로 끝나지 않는이 악순환의 고리 아닙니다
언제까지 이래야 않기 때문에? >> [학생]는 당신이 한 일에 도달합니다.
당신이 한 일에 도달합니다.
당신이 8 사람들과 시작 될 수도 있고 내가 무슨 말을하더라도 자, "이 사람들의 왼쪽 절반을 정렬
이 사명은 "그럼 말,"어떻게 왼쪽 절반을 정렬합니까? "
"자, 여기 12 명을 정렬합니다." 그리고 당신은 같은거야 "좋아, 좋아."
"어떻게 사람들의 왼쪽 절반을 정렬합니까?"
"그냥 여기에 1 명을 정렬." 이제 화려한 계시은 무엇입니까?
나는 1 인을 정렬해야합니다. 완료. 어떤 작업을 수행 할 필요가 없습니다.
하지만 지금은이 사람을 정렬해야하지만 한 사람, 상관이야.
>> 그래서 마법은 분명이 세 번째 단계에 있습니다 정렬 절반을 병합합니다.
따라서 병합 정렬이 뛰어난 통찰력을 필요 당신은 큰 문제를 어기면
이 작은 동일한 크기의 문제로
그리고 끝 부분에있는 작은 솔루션을 함께 접착제, 그냥,
나는 우리가 훨씬 더 [터치 소리]를 많이 할 수 있다는 제안
선택 정렬이나 삽입 정렬의 초과했습니다.
사실 난 반 시간 동안이나 그렇게 무시하고있어,하지만 난 정말 무슨 일이 일어난 거지?
오늘 밖에. [지 - 잉 소리] [웃음]
그래서 우리는 우리의 친구 롭 보덴에서 약간의 도움을 볼 수 있는지 보자.
병합 정렬의 과정에서 2 개의 대형 단계가 있습니다.
첫째, 지속적으로 절반으로 컵의 목록을 분할
우리는 그들, 그냥 1 컵과 목록의 무리가 될 때까지.
목록 홀수가 포함되어있는 경우 걱정하지 마세요
당신은 그들 사이 완벽하게 깨끗한 몫을 할 수 없습니다.
그냥 임의로 추가 컵 인치를 포함하는 목록을 선택
그럼이 목록을 분할 보자.
이제 우리는이 목록을 수 있습니다.
이제 우리는 4 목록이 있습니다.
이제 우리는 각 목록에서 컵 8리스트를 갖추고 있습니다.
그래서 단계 1 거에요.
단계 2 우리는 반복적으로 우리가 전에 배운 병합 알고리즘을 사용하여 목록의 쌍을 병합합니다.
108 15 병합 우리는 목록을 15, 108이 생깁니다.
50 4 병합 우리는 4, 50이 생깁니다.
8 42 병합 우리는 8, 42에서 소개합니다.
23와 16을 병합 우리는, 16과 23이 되죠.
지금 우리의 모든 목록의 크기는 2의합니다.
4 목록의 각이 정렬되고 있다는 사실을 알 수,
그래서 우리는 다시리스트의 쌍을 병합 시작할 수 있습니다.
15 108 4 50 병합하면 우리는 먼저 다음 15 4을
다음 50 후 108 번.
8, 42 및 16, 23을 병합 먼저 다음 8 16, 가져
다음 23 다음 42.
이제 우리는 크기가 4 단 2 목록을 가지고 각각의가 정렬됩니다.
이제 우리는 이러한 두 목록을 병합합니다.
먼저 우리가 4를 손에 넣은 다음 우리는 8을, 우리는 15을
16 23, 42 및 50과 108.
그리고 우리는 끝났어. 우리는 지금 정렬 목록을 수 있습니다.
>> 롭은 우리가 아직 완료하지 않은 것을 활용하는 것 같아요.
이 제안되었지만, 우리는 실제로하지 않았어.
그는 제안 컵 물리적 짓을했습니다
그는 시간 외에 어떤 리소스를 소비했다. >> [학생] 우주. >>는 공간이었다.
여기 공간을 한 곳에서 그는 이중 레벨 테이블이 종류가 있다는 사실
여기 아래 공간은 실제로 사람이 두 배나 많은 공간을 사용한다는 뜻되었다
삽입 정렬, 버블 정렬, 또는 선택 정렬 - - 지금까지 알고리즘의 등
그는 앞뒤로 이동 일인데이 추가 공간을 활용 한
순서로 일을 유지하면서.
우리가 정렬 목록에있어 기분이 비록 그 때까지 시간이 좀 걸 렸어요처럼, 그 느꼈다.
현실에서는, 어떤 롭 일이 것은 정확히이 알고리즘했다.
그는 먼저 크기 N의 문제를 가져다가 왼쪽 반 오른쪽 절반에를 나눈 값입니다.
그는 컵을 이동 때입니다. 그리고 그 과정을 반복했다.
그는 여기 이상 여기에 2 개 중 2 개의 세트로 4 나눈 값입니다.
그리고 그 과정을 반복하고 이러한 다양한 컵 각 1 2 세트로 2 분할.
화려한 기회가 발생 곳 고.
이야기 그 시점에서, 롭, 크기 1의 8 목록을 가지고
하는 모든이 이미 정렬되었습니다.
>> 그래서 그 사람은 뭘를 진행 했죠?
Pairwise 그는이 정렬 목록이 정렬 목록을 데리고을 통합.
그리고,이 하나를 들고 그들을 병합, 다음이 하나를하고이를 통합
다음이 하나 그들을 병합.
그리고 그가 무슨 다음 짓을 한거야?
그 후 더 큰 목록을 다시 합병 후 큰 목록을 다시 합병.
당신은 지금 막 직관적으로 생각해면, 정말이 대체 뭘 한 거지?
그는 반으로 반으로 반으로 반으로 문제를 분리했습니다
이 슈퍼 작은 목록을 보려면 여기를 클릭하십시오.
그럼 그 사람은 더블, 더블, 더블, 더블를 결합하는 것 같아요.
그래서 그는 우리가 지금까지 본 적이만큼 작품으로 두 번 짓
분리와 정복,하지만 큰 거래를 포함하는 걸로.
두 배는 더 일을 그렇게 큰 거래되지 않습니다. 단지 상수 요소입니다.
그리고 전에도 많이 우리의 산술 식처럼, 단지 일정한 요인을 건너 갈거야
2 배처럼. 누가 무슨 상관이야? 아직도 단계 많이의 2 배, 2 억 이죠.
그래서이 합병 단계는 키 통찰력을 것 같습니다.
의 전에 단지 숫자 이런 식으로 걸어 가자 - 아, 그건 아직 계속 할 수 없습니다.
의는이 숫자 만 실제로 어떻게되는지 볼 수 통과 보자.
이 대부분이 좀 가난한 사람의 애니메이션입니다.
의이을 제안 보자.
병합 정렬의 실행 시간은 - 우리가 이런 이야기의 방법이 필요합니다.
이건 수학이 아니에요,이 자신을 표현하는 간결 방식이긴합니다.
따라서 T는 시간을 나타내며, n은 무엇을 제시 하는가? >> [학생]의 크기 -
>> [Malan] 문제의 크기, 사람의 번호입니다.
그래서 N 사람들을 정렬 할 수있는 실행 시간 시간 0 금액이 될 거라 주장하고있어
N은 1 컵 또는 전혀 컵이 경우 정렬 아무 상관이 없기 때문에, 2보다 작습니다. 경우
하지만 더 일반적으로, 내가 실행 시간이 N 요소를 정렬 할 것을 제안거야
그 왼쪽 절반을 정렬하는 데 걸리는 시간을 더한 오른쪽 절반이 될 것입니다
플러스 -이 추가 + n은 뭐죠? >> [학생] 병합 정렬.
[Malan] 당신이 여기 N / 2 요소가있는 경우 때문에 실제로, 합병있어
당신이 여기 N / 2 요소를 가지고이 그들을 병합하는 방법을 많은 시간이 걸립니까?
그냥 롭처럼, 당신이 여기이 뽑은해야 아마, 여기에 뽑아 내다
여기에 털을 뽑아 내다, 여기 다듬 여기에 뽑아 내다.
당신은 한 번 컵의 각을 터치해야합니다.
4 컵 + 4 컵이 있다면 그리고, 그 8 컵입니다
또는 더 일반적으로, 8 N 컵.
따라서 합병 단계는 우리는 N으로 표현할 수
그 말 그대로 횟수 물리적으로 접촉 로브를 포함
그 스티로폼 컵 중 하나입니다.
이제 임의의 예를 한번 해보자 구.
16 컵이 있다면, 어떻게 롭의 알고리즘, 16 컵을 사용하여 정렬의 실행 시간있어?
이 8 컵을 정렬 할 걸리는 시간이 2 배 양
여기, 우리가 8 컵을 가지고 있기 때문에, 8 컵.
난 정말 우리가 잠시 동안 T로 일반화하고 얼마나 오래 걸리는지 모르겠어요.
누가이 몇인지 아는 사람?
하지만 지금은 반복적으로 또는 반복적으로 같은 질문을을 정렬 할 수 있습니다.
8 컵을 정렬하는 데 시간이 얼마나 걸리나요?
내가 무슨 말을하려고 해요 8 컵, 이건 4 컵 + 4 컵을 정렬하는 데 걸리는 시간의 양을 필요
그것들을 함께 병합.
좋아요. 우리는 이미주기에 있어요. 4 컵을 정렬하는 데 얼마나 걸리나요?
이 4 컵을 정렬하는 데 걸리는 시간은 2 컵 플러스 2 컵 정렬 플러스 합병 과정입니다.
좋아요. 2 컵을 정렬하는 데 얼마나 걸리나요?
2 컵은 1 컵을 정렬하는 데 걸리는 시간의 양이 플러스가 다른 컵을 정렬하는 데 걸리는 시간입니다
플러스가 병합하는 데 걸리는 시간의 양이되는데,이 단 2 명입니다.
>> 좋아요. 마지막 질문입니다. 1 컵을 정렬하는 데 얼마나 걸리나요?
여기에 우리가 이전에 죽이 잘 맞는 친구 예측하는 기본 케이스입니다.
이 문제의 가장 작은를 정렬하려면 어떠한 노력이 필요 없다는 사실
수단 이제, 초등학교 스타일의 종류,
우리는 인치 다시이 숫자를 연결해 시작할 갈 수
우리는 지금 1 T가 뭔지 알아, 그래서 제가 1 T 0에 연결 할 수 있습니다.
그때 에게라도에 연결할 수 있습니다 (2)의 T, 나에게 대답을 할 것입니다.
그건 내게 내가 에게라도에 연결할 수 4 T를 제공 할 것입니다.
그건 내게 내가 에게라도에 연결할 수 8 T를 제공 할 것입니다.
그리고 실제로이 답변에 꽂아 그 수학을 할 경우,
그때 나는 16 T 64 드리고 있습니다.
그리고 64 무엇을 나타 냅니까?
T는 16 인 경우, 예, 16 시간 4입니다.
그래서이 물건의 실행 시간이 좀 병합라고 지금 주장 -
이 우리가 지금까지 본 것들 중에서 가장 좋은 될 것입니다 -
라고 할 것 N 로그 N입니다
얼마나 많은 시간이 반으로 컵을 아주 많이 분할 롭 수 있기 때문에? n을 기록합니다.
그것은 전화 번호부의 예와 같은, 이것은 그 자체 계산 예를 들어 같은입니다.
>> 몇 번 반으로 무언가를 나눌 수 있습니까?
그러나,이 병합 단계가 있습니다.
당신은 다시 다시 다시 이분의 일에 컵을 나누어해야 할 수도 있습니다
하지만 자네는 자네가가는 때마다 병합해야합니다.
그리고 우리는 N 개의 컵을 통합하는 N 조치를 취하고 있다고 밝힌 바있다
당신은 한 잔을 뽑아 낸하기 때문에, 한 잔을 뽑아 낸, 당신은 한 번 잔을 터치해야
단지 롭처럼 했어요.
우리가 뭔가 로그 n 번을하고 우리는 그 반복의 각에 대한 N 일을하고있는면은,
그 halvings 각, 우리는 n 번 로그 N 수 있습니다.
우리가이 예제에서 16에 플러그를 꽂으면, 16 시간 16 로그인 -
제가베이스를 그려 적이 없다 때문에이 지금의 경우 이유에 대해 걱정하지 마십시오 -
하지만 16 기지 2 로그, 시간 4 64 16 4.
그러나 반대로, 우리는 16의 숫자를 버블 정렬이나 선택 정렬이나 삽입 정렬을 사용했을 경우,
여기서 n은 16 경우 실행 시간은 어떻게 갔었을거야?
이는 256입니다, 16 제곱, 귀하가 매우 모든 수학을 준수하지 않은 경우에도 것입니다
256은 64보다 큰 수 있습니다. 그건 정말 여기에 마법의 테이크 아웃입니다.
그리고 pset에 의지으로 작은 예제에서이 일을 일하는 실현
그 훨씬 더 직관적 모두 있습니다.
하지만 실제로는이 알고리즘의 느낌의 관점에서 어떤 의미인지하면이 있습니다 :
우리가 실제로 여기에 병합 정렬을 보면 - 내가 여기이 창에 올려 보자 -
이게 우리가 이러한 알고리즘의 모든 3이된다 약간 다른 예입니다 -
버블, 선택, 그리고 병합 - 옆으로 단 측면을.
>> 그들은 모두 랜덤 바 시작했으며, 좋네요.
아무도 다른 이상의 근본적인 이점이 없습니다.
나는 순간에 갈거야하면 이러한 애니메이션의 각 클릭 - 시작 시작 시작 -
제가 할 수있는 한 빠른 속도로, 그래서 그걸 동시에 약, 그들은 모든 시작,
시간을 실행하는 버블 정렬의 최악 사건이 무엇인지가 생각 해요? >> 제곱 [학생] N.
N은 제곱. 시간을 실행하는 선택 정렬의 최악의 경우는? N은 제곱.
그리고 병합 정렬은 분명히 있습니다 - 당신은 매우 모든 수학을 준수하지 않은 경우에도, 지금
그것은 훨씬 더 직관적으로 시간이 지남에 따라이 될 것 - 우리가 주장 n 번 로그 N입니다.
그리고 로그가 N보다 엄격하게 적은 N 일단 큰 숫자를 가지고 있기 때문에하면,
n 번 로그 n은 n 번보다 작은 n 또는 N 제곱입니다.
그래서, 사실 실행 시간의 측면에서 더 나은 알고리즘을 할 기분이
n 번 로그 N 등의 제곱 N에 반대? 여기 우리는 간다. 를 클릭, 클릭, 클릭합니다.
>> 그게 병합 정렬과 같은 무언가를 사용하는의 의미입니다.
우리는 순간을 갖추고 있습니다. 여기서 무슨 일이 일어날 지 보자.
누구 돈 버블 정렬에 ㅠ ㅠ?
그것은 오히려 가끔 입력에 따라 달라집니다.
어디 봅시다.
이리와. 그는 따라 잡는 느낌. >> [학생] 버블 정렬로 이동합니다!
[학생들이 웅성 대는 소리]
[Malan] 네, 네.
[웅성 대는 학생]가,가,가!
[박수] [모두 환호]를
이제 한 마지막으로, 최종 데모와 함께하면 수학은 주위에 마음을 포장하기 조금 어렵습니다
아니면 시각화 종류의, 당신은 실제로 속도를들을 수
다르게 서로 다른 알고리즘.
이와 같은 사실은 실제로 동료가 들리는 것을 만든 애니메이션 사람입니다
교환의 과정과 바의 높이.
우리가 보 겠지만, 몇 가지 더 정렬 알고리즘은 사람들이 생각 한 그쪽 있습니다.
첫 번째 사람은 삽입 정렬 될 것입니다, 그리고 이것은 날고
그리고 당신에게 어떻게 이러한 다양한 알고리즘 작업의 음성 느낌을 제공합니다.
다음은 삽입 정렬입니다.
[전자음]
[Malan] 버블 정렬.
[전자음 빠르게]
[Malan] 선택 정렬.
[전자음 빠르게]
[Malan] 병합 정렬.
[전자음]
[웃음] [삡는 속도가 느려]를
[Malan] 그​​놈 정렬.
[전자음]
>> 이 CS50입니다. 우리는 다음 주에 볼 수 있습니다. [박수와 환호]
>> [CS50.TV]