>> [음악 연주]
>> DAVID J. 마란 : 좋아요.
그래서 다시 오신 것을 환영합니다.
이 CS50, 그리고이다 주일의 끝입니다.
>> 그래서, 지난 몇 주 동안 기억 우리는 꽤 지출 봤는데
C에서 프로그래밍에 대한 구문에 대한 시간입니다.
당신이 아직 있다면 그리고 그것은 아주 정상 수, 문제 설정이 어려움을 겪고
벽에 머리를 두드리는.
그것은 암호화 된 예측 오류 메시지의 버그는 당신
아주 쫓아 수 없습니다.
때문에, 안심, 그 중 단지 몇 주간의 시간 당신은 다시 살펴 보겠습니다
카이사르 같은 것들, 그리고 [? V-genair?] 어쩌면 균열 및
당신이 와서 얼마나 멀리 실현 시간의 짧은 기간합니다.
그 어떤 위로의 경우에, 지금 거기에 끊지.
>> 오늘날, 그러나, 우리는 전환 시작 가지 높은 수준으로.
그리고 우리는 당연시하기 시작합니다 너희들은 프로그램하는 방법을 알고, 또는시
의 시작 최소 그 안락 수준.
그리고 우리는 어떻게 우리가 할 수있는 고려하기 시작합니다 더 많은 프로그램을 설계에 대해 이동
효과적으로.
우리는 최적화에 대해 갈 수있는 방법 우리의 알고리즘의 효율성 및
일반적으로 더 해결 흥미로운 문제.
그리고 그 당연한 시작 우리가 원한다면, 우리는 어떤을 코드 수
우리가 염두에두고 예.
그래서 오늘, 우리는 키보드를 만지지 마십시오 코드의 형태.
그것은 훨씬 더 높은 수준의, 그리고 것 궁극적으로 문제 해결에 대한.
>> 그래서 그 점에 도착, 내가 제안하자 그 다음의 7
사각형 뒤에 일곱 문을 나타냅니다 이는의 전체 무리입니다
숫자, 그중 번호 50입니다.
날이에이 프로젝트하자 여기뿐만 아니라 화면을 표시합니다.
그리고 우리가 자원 봉사를 필요로하는 제안 나에게 앞 번호를 찾을 수 있도록
보려면 여기를 클릭하십시오 인터넷.
핑크에 올라와.
좋아.
당신의 이름은 무엇입니까?
>> 제니퍼 : [들림]
>> DAVID J. 마란 : 네?
>> 제니퍼 : 제니퍼.
>> DAVID J. 마란 : 제니퍼.
모든 권리, 제니퍼.
만나서 반가워요.
올라 와요.
그래서이 여기에 일곱 문, 그리고 무엇 난 당신이 여기 우리를 위해 할 싶습니다
귀하의 급우의 앞에, 우리에게 숫자 50을 찾을 수 있습니다.
번호를 찾으려면, 당신은 슬쩍 뒤에 수 간단하게 터치하여 이러한 문의
문 하나 그것에 해당 번호를 공개합니다.
그리고 어디 보자 얼마나 빨리 우리에게 숫자 50를 찾을 수 있습니다.
>> 15.
16.
50.
잘 했어.
좋아.
제니퍼에 대한 박수 라운드.
>> [박수]
>> 좋아.
그래서 전략은 무엇습니다 , 50 번호 찾기?
>> 제니퍼 : 음, 아마하면 생각 -
[들림]
>> DAVID J. 마란 : 아.
그것을 1 초 제공합니다.
그래서 전략을 위해이었다 , 50 번호 찾기?
>> 제니퍼 : 그래서 난 그냥 시작 하기 시작 것을 첫 번째 숫자
아마 경우이고, 그때 생각 그들은 분류하고, 난 그냥 계속 거
상위에 도청?
>> DAVID J. 마란 : OK.
그리고 우리가 발견하는 것 경우 수합니다.
하지만, 다시 껍질 레이어를하자 다만 조금, 당신은 가고 싶어
앞서와 다른 문을 밝혀 당신이 선택한 수 있을까?
>> 제니퍼 : 오, 이런.
>> DAVID J. 마란 : 아.
>> 제니퍼 : 그래서 난 그냥 운이 좋았어요.
>> DAVID J. 마란 : 그래서 당신은 운이 좋군.
좋아.
그렇게 나쁘지 않다.
하지만 그 흥미 통찰력, 오른쪽?
, 당신은 가정, 당신은 얻을 않은 경우 실제로, 조금이 운이.
하지만 숫자가 있다고 가정하면 정렬 좀 더 정확하게 할 수 있습니다
그 영향을 방법에 대한 당신의 행동?
>> 제니퍼 : 그들은이 정렬 된 경우에, I 최대에 어쩌면 작은 생각했다.
>> DAVID J. 마란 : OK.
>> 제니퍼 : 또는이 끝났다면되고 작은에 그 큰, 정말 큰.
>> DAVID J. 마란 : OK.
그래서 최소로 큰, 또는 최소에서 최대로.
하지만 내가 제안하자, 당신이 있다고 가정 불운 받고, 그리고 가정 그들이
사실, 분류되지 않은, 얼마나 많은 그 문 당신은 엿에 있었다 수
그 최악의 경우 뒤에?
>> 제니퍼 : 그들 모두.
>> DAVID J. 마란 : 그들 모두.
그럼 일반화하자 N로합니다.
가 7로 발생하지만하자가 더 일반적으로에서의 N 문이 말한다
여기에 화면을 표시합니다.
따라서 최악의 경우에, 당신은 것 7 문, 또는 n 문 뒤에 볼 수 있습니다.
그리고 이것은 정말의 비트의입니다 운 오늘,하지만 정말 선형의
종류의 알고리즘, 비록 당신 주위 건너 뛰는 종류이었다.
이 박람회는 무엇입니까?
>> 제니퍼 : 네.
>> DAVID J. 마란은 : 글쎄, 어디 보자 한 경우 고객님의 전략 변경 난 우리로 이동하는 경우
여기에 우리의 두 번째 예제 7 개의 다른 문.
같은 번호 만이 시간은 그들이 정렬됩니다.
될 여기에 귀하의 전략은 무엇입니까 당신의 마음에서 몰아 내려고 무엇을
다른 숫자였다 -
>> 제니퍼 : OK.
>> DAVID J. 마란 : - 이전?
>> 제니퍼 : 시작하자 첫 번째로.
>> DAVID J. 마란 : 좋아요.
첫 번째로 시작합니다.
4.
이제 어디로 갈, 왜?
>> 제니퍼 : 4 정말 작습니다.
그들은 일종의 어쩌면 작은거야 그래서 만약 큰에, 그것은해야
- 두 배, 그리고해야합니다.
>> DAVID J. 마란 : OK.
자, 당신이 생각하는 보이지?
>> 제니퍼 : 마지막 하나를 수행하십시오.
좋은.
>> DAVID J. 마란 : 아주 잘 했어.
좋아.
>> [박수]
>> DAVID J. 마란 : OK.
그래서 당신은 실제로 일을하고 당신이있어 무섭게 때문에
아주 잘하고 있어요.
어느에 우리가 할 수없는 단풍 특정 지점을 확인합니다.
그래서 여기 롤백을 시도하자.
>> 제니퍼 : OK.
>> DAVID J. 마란 : 아주 좋아요 그럼에도 불구하고, 수행.
그래서 당신은, 처음에 시작 당신은 그런 사 더라
끝으로 이동.
하지만 당신은 운이하지 않은 가정 , 거기에 가정 50
다른 곳이었다.
무엇 번째 단계가 있었나요?
>> 제니퍼 : 처음으로 돌아갑니다.
>> DAVID J. 마란 위로 가기 처음으로.
OK, 당신은 감동 한 것이다 8였습니다 문.
좋아.
그래서 50이 아니다.
어디 다음 보았다까요?
>> 제니퍼 : 내가하지 않은 경우 그들은 분류 알고 있습니다.
>> DAVID J. 마란 : 수정.
글쎄, 당신은 한 알고 그들은이 정렬되었습니다 -
>> 제니퍼 : 오, 그래, 알지 못했다.
>> DAVID J. 마란 -하지만 당신은하지 않았다 50는 아직 어디에 있었는지 알아?
>> 제니퍼 : 그냥 계속.
>> DAVID J. 마란 : 좋아요.
확인을 클릭합니다.
계속.
좋아요, 내가 작업 할 수 있습니다.
>> 제니퍼 : OK.
>> DAVID J. 마란 : 당신은 이제 있다면 계속하려고, 무슨하여
알고리즘에 백업 이양.
>> 제니퍼 : 선형 -.
>> DAVID J. 마란 : 그것은 선형의 일종이다.
그러나하자, 내가 제안하자 내가 그 자리에 넣어.
내가 페이지를 새로 고칠 수 있습니다.
같은 번호, 같은 배열, 같은 문.
그러나의 첫 날에 다시 생각한다 우리가 전화 번호부를 찢어 클래스
절반의 종류, 어떤이었다 거기에 우리의 전략?
>> 제니퍼 : 중간에서 시작합니다.
>> DAVID J. 마란 : OK.
그래서 중간에서 시작합니다.
그럼 가서 그를 시뮬레이션 할 수 있습니다.
에 의해 중간에서 시작 그 문을 드러내는.
그래서 번호 16.
그래서 강한 사람이 무슨 짓을했을 것입니다, 누가 반으로 전화 번호부를 찢어
다음 추측을 얻으려면?
>> 제니퍼이 반으로 이동합니다.
>> DAVID J. 마란 : 그리고 왜 오른쪽?
>> 제니퍼 : 그들은 있다면 일종의 최소의 최대로, 다음 50이어야한다
그 말에.
>> DAVID J. 마란 : 좋은.
완전히 합리적.
그래서 전화 번호부처럼, 당신은으로 이동 오른쪽으로 왼쪽으로 반대하지만, 여기에
키 테이크 아웃입니다.
당신은 지금, 멀리 던져, 또는 벗길 수 이 문제의 절반, 안 떠나
7 문,하지만 정말 그냥 3.
어떤의 약 절반 문제의 크기입니다.
좋아.
그래서 지금 당신이 할 무엇을 당신이 바로 이동 후에 수행?
>> 제니퍼 : 그래서 16, 아직도 꽤 작 50을 기준으로, 그래서 어쩌면 내가 노력하겠습니다
이와 같은.
>> DAVID J. 마란 : 좋아요.
42.
좋아, 이제 무엇의 말하고 본능?
>> 제니퍼 : 내가 멀리 던질 수 이 후 단지 -
>> DAVID J. 마란 : OK.
잘, 당신은 멀리 던질 수 거기에 왼쪽 절반입니다.
>> 제니퍼 : -이 하나를 선택합니다.
>> DAVID J. 마란 : 그리고 권리가 있습니다.
>> 제니퍼 : 네.
>> DAVID J. 마란 : 그것은 어렵다 그럼에도 불구하고 만있을 때, 아마 볼 수
7 문, 지금 생각해 의 일관성
당신은 방금 적용한 알고리즘입니다.
앞의 경우에, 당신은 한 컸다, 행운.
하지만 당신은 휴리스틱을 사용했다 내가 말할 것입니다.
당신은 당신의 본능의 종류를 사용하고, 꽤의 경우는, 분류 알고
처음에 작은, 분명히, 우리는했습니다 오른쪽으로 더 가야.
그러나 어떤 의미에서, 당신은 운이 좋군 아마 이것은 100 번 이었기 때문에
어쩌면 50 중간에 더했습니다.
아마 50 여기에도했다.
>> 하지만 당신은 조금 다르게 뭘했는지 이 시간이되었다, 당신은 같은 일을했다
또 다시.
내가 주장하는 무슨 단지 ,이기는하지만 전화로 영향 않았다
책 예를 들어, 많은 일이있다 더 많은 알고리즘, 그리고 훨씬
적은 특수 맡았다.
훨씬 더 본능적.
그래서 하루의 끝에, 어떻게 것 당신의 효율성을 설명
당신이 가서 첫 번째 알고리즘 대, 왼쪽에서 오른쪽으로
여기에 두 번째 알고리즘?
>> 제니퍼 :이 사람이해야한다, 같은, 어쩌면 시간을 절반, 혹은 그 이상, 그래.
>> DAVID J. 마란 : OK, 어쩌면 더.
의 그에 약간 세게 밀어 보자.
정말 무엇을, 우리는이 문제를 계속하는 경우 논리는, 우리는 확실히 절반 ​​가까이 떨어졌다
이 두 번째 알고리즘 실행 시간 의 절반을 멀리 던져
수 있지만, 우리는 다음에 무엇을 했는가 제니퍼 밝혀 반복,
두 번째 숫자?
>> 우리는 다시 문의 수를 절반.
그리고 우리는 그 후 어떻게 한 경우 놀에 더 많은 문이 있었다?
우리는 다시 절반, 그리고 것 다시, 다시.
그리고이 모든 너희들 같았다 의 첫 주에 서
당신이 아래 앉아 수업, 반, 반 의 당신은 당신의 절반을 앉아
한 고독한까지 앉아 영혼이 서 있었다.
그리고 우리는 말했다의 실행 시간 즉, 취한 단계의 수는 있었다
어떤 순서에?
>> 스피커 1 : [들림]
>> DAVID J. 마란 : 그래서 로그베이스 N 2, 아니면 그냥 단순히, N으로 로그인합니다.
그래서 대수인가.
그리고 그래프는 직선이 아니었다 단지 더 악화있어 즉,이었다
하지 않았다이 흥미로운 곡선 시간이 지남에 그렇게 나쁘지 얻는다.
그럼이 아이디어를 보유 할 수 있습니다.
의 제니퍼 감사하자.
올라 오기를위한 감사합니다 순전히.
그리고 초 한.
어떤 책상 램프 없음 오늘,하지만 우리 CS50 스트레스 공을 가지고 않습니다.
>> 제니퍼 : 야호.
>> DAVID J. 마란 : 좋아, 여기에.
침해 주셔서 감사합니다 여기에 스트레스까지.
좋아.
그럼 보자 우리가 지금은 할 수있는 경우 조금 더이 공식화.
그래서 다시 우리가 무슨 짓을했다 우리가했던 본질적으로 같은 것을
첫 주에있다.
오히려 말보다 단 선형과 우리가 묘사 알고리즘
이전에이 직선으로, 그것에 의하여, 우리가 한 번 더 문을 넣으면
화면이 다음 제니퍼 것 잠재적으로 지켜 볼 수밖에 없었습니다
또 하나의 문 뒤에.
우리는 두 개 더 문을 넣어, 그녀는해야 할 수도 있습니다 두 개 더 문 뒤에 볼 수 있습니다.
>> 그리고이 직선이 있었다 의 크기의 관계
x 축, 말에 대한 문제, 그리고 는 데 걸리는 시간
Y를 해결한다.
하지만 내가 암시 된 사진 이번 녹색 선이었다.
녹색 의도적 때문에 그냥 기분이 좋았다.
이론적으로, 우리는 그것을 알고리즘을했을 때 전화 번호부 때, 우리는 그것을했다
너희들은 서로를 계산하고, 함께 두 번째 경우에, 때 제니퍼 단지
여기에 그것을했다, 그것은 일종의이었다 근본적으로 더 나은.
그냥 배 빠른 속도로되지 않았기 때문에.
그것은 빨리도 네 번이 아니었다.
그것은 무엇에 전적으로 의존했다 입력의 크기에 관해서는, 얼마나 많은
궁극적으로 갔다 단계를 반복합니다.
>> 그리고 우리 모두가 걸렸다 있도록이 간단한 아이디어 전화 번호부 부여를 위해,
마찬가지로 적용 할 수있다 이 같은 뭔가.
그리고 더 부담 될 수 있습니다 당신은 수도로 알려져
분할과 정복, 상상.
하지 우리가 무슨 짓을했는지는 달리, 물론, 전화 번호부.
>> 하지만 의사, 리콜이 있었다.
그래서 우리는 다시 이렇게하지만, 기억하지 않습니다 그 첫 주, 우리 모두 일어 서서
그리고 당신의 반은 절반, 앉아서 당신은 앉아서 당신의 절반 앉았다.
그 알고리즘으로 구현되었다 그의 부정 방법의 비트, 그
나 하나가 계산되지 않았습니다 근본적으로,보다 효율적으로.
그 경우는 활용되었다 보조 리소스.
일종의 다중 CPU를 여러 뇌, 여러 똑똑한 사람들
객실 날에서 뭔가 얻을 수 있도록 하였다 뭔가 선형
뭔가에서, 로그 뭔가 녹색 빨강.
>> 그러나이 경우, 제니퍼 혼자 할 수 있습니다 근본적을 향상
그녀의 첫 번째 알고리즘의 성능에 의해, 다시 조금 더 생각.
그리고 지금, 그것을 구현하는 시간이되면 이러한 일들이 파악
당신은을 작성할 수있는 코드의 줄 당신은 그들을 다시 반복 할 수있는
다시, 다시, 정렬 루핑 패션한다.
당신이하지 않을거야 때문에, 제니퍼와 같은 사치품에, 처음에 한
다만, IFS의 전체 무리를 가지고 말 음, 첫 번째 번호가 4 인 경우는,
저 끝까지 뛰어 보자.
그 숫자가 너무 크다면, 우, 저를 임의로 다시 이동하자
두 번째 요소.
당신은 많이있을거야 찾을거야 더 공식화 우리 인간
매우 합리적으로 당연시 추론하지만, 컴퓨터는이다
당신이 그것을 말해 무엇을 할 것.
>> 지금이 아주 재미있다 의미.
이 그래프는 일종의 일종의하기위한 것입니다 시각적으로 압도하지만, 통지, 여기서
이 그래프에서 직선입니까?
선형 그래프는 어디에 우리는 n을 호출하는?
글쎄요, 그것은 아래쪽으로 일종의의 이 그림의 오른쪽?
우리가 한 모든 우리가 일종의을했습니다 그래서 x 축과로 축소해서
y 축에 어떤 의미를하려고합니다 곡선의 다른 유형처럼 보입니다.
>> 그리고 수학의 특성 표현은 오늘 그렇게 중요하지 않습니다
많은,하지만 많이 발견 할 수있을 것입니다 보다 훨씬 더 나쁘다 알고리즘
선형 뭔가.
사실, 삼승 N은 아주 나쁜 보인다.
2 n으로는 아주 나쁜 보인다. 제곱 N은 아주 나쁜 보인다.
그리고 우리는 볼 것이다 무엇을 그 중 일부 실제로 오늘날 수 있습니다.
및 로그 N 불량으로 느끼지만하지 않습니다 n보다 나은 N의 로그베이스 2입니다.
하지만 당신은 알고, 심지어는 있었을 것이다 더 놀라운 경우 제니퍼, 또는 우리 경우
첫 주에 도달했다 N의 로그 로그 뭔가.
>> 그래서 다른 말로,이 모든이의 제에 대해 가능한 솔루션의 범위
문제가 있지만, 여기에도 통지 무슨 일이 일어날거야.
이 곡선의 I가 축소 될 때, 그 절대이 될 증명할 것입니다
이제 화면에 사람의 최악의?
그래서 N 제곱 꽤 보인다 순간에 나쁜.
그러나 우리는 축소보다의를 참조하는 경우 것 x와 y 축,
궁극적으로 지배?
그래서 실제로 해당 2 밝혀 N, 그리고 당신은하여 알아낼 수 있습니다
일부 점점 더 큰에 연결 숫자, 당신은 볼 것이다 그 2에
N, 참으로, 더 큰 더 빠르게 가져옵니다.
우리가 정말에, 2 축소하는 경우 N 알고리즘은 절대적으로 짜증.
나는이 걸릴 것입니다 의미 시간이 꽤
컴퓨터를 이탈합니다.
>> 하지만 당신은 특히 시간이 지남에 볼 수 있습니다 미래의 문제와 세트도
최종 프로젝트는 데이터입니다 세트, 모든 권리 커질?
심지어 페이스 북의 첫 번째 버전에서, 친구의 수와 같은
등록 된 사용자의 수는 큰있어 당신의 전화를 그것을 정렬 할 수 있습니다
, 선형 검색으로 뭔가를 구현 또는 매우 간단한 정렬
오늘 우리가 보게 될 알고리즘.
당신은 열심히 생각하기 시작해야 이러한 문제에 대한 더.
및 문제 장소의 종류 등 페이스 북, 구글, 마이크로 소프트,
그리고 작업을 다른 사람이 정확히 질문 빅 데이터 정렬의 종류
점점 이러한 일.
>> 좋아.
그 두 번째 제니퍼의 성공 때문에 알고리즘은, 솔직히, 그녀는 굉장했다
물론 처음 만하자 그 행운으로 작성하는 우리
이 점을 만들 수 있습니다.
두 번째 경우에, 그녀는을 활용 다시 반복 알고리즘
당연한 다시, 그러나 그녀는했다 우리가 허용 한 특정 가정
그녀,하지만 그녀는 몇 가지 세부 악용 그녀가하지 않은 두 번째
처음.
어떤 이는입니까?
>> 목록이 정렬 된.
목록이 정렬 된만큼 마자, 우리 제니퍼 할 수 있었다고 주장
근본적으로 더 나은.
7 문, 그래, 그 관심이없는 하지만 우리는 7 백만 문입니다 그것을 가정합니다.
N의 기록은 확실히 것입니다 훨씬, 훨씬을 수행 할 수
장기적으로 빨리.
하지만 그녀는이했다 문 그녀를 분류.
지금, 나는 그 일을 자유를했다 컴퓨터 화면에 미리
여기에,하지만 제니퍼 가정 자신 그렇게했다?
가정이 질문에 문 표시 데이터베이스에서 데이터 또는
페이스 북에 등록 된 친구, 또는 인터넷에있는 모든 웹 페이지가
다양한 웹 사이트는해야 할 수도 있습니다 인덱스 이상 검색 할 수 있습니다.
>> 그냥 원시 데이터를 가지고 있다고 가정하자 설정하고 그것은 당신에게 남은 나에
제니퍼는 정렬을 할 수 있습니까?
즉, 오히려 우리가 대답해야 질문, 잘, 얼마나 많은 시간
제니퍼, 심지어 저를 찍은 것 사전에 그 숫자를 정렬 할 수 있도록
그녀는 활용할 수있는?
오른쪽?
의미는 물론이기 때문에, 그것을 정렬하는 나에게 꽤 걸리는 경우
도대체 당신을 걱정하는 숫자, 너무 빨리 50과 같은 번호를 찾을 수 있습니다,
보다 제니퍼의 경우,처럼 우리는 더 총 시간의 양을 압도
그것은 사전에 물건을 정렬하여 갔다?
>> 그래서 우리가 할 수없는 경우 보자 여기에 그림을 그린다.
나는 갓 더 많은 스트레스를 가지고 공, 도움이되는 경우
여기에 얼음을 깰.
그리고 당신은 상관하지 않을 경우, 우리는 일곱 자원 봉사자가 필요합니다 -
OK에.
와우.
그래서 우리는 지출하지 않아도 책상 램프에, 그것은 보인다.
좋아.
그렇다면 앞의 두 당신에 대해.
다시 두 사람 어때요.
그래서 네입니다.
당신은 어때요 앞 다섯, 여섯 일곱.
거기.
당신의 친구는 당신을 가리키는 그래서 당신은 상을받을.
>> 좋아.
올라 와요.
왜 우리는 당신이 필요가 없습니다 사람들은 이상 여기에 온다.
나는 당신에게 각 수를 줄거야.
그리고 가서 자신을 준비 동일 무엇을
화면에 묘사.
>> [목소리를 개재]
>> DAVID J. 마란 : 웁, 죄송합니다.
버그가 수정되었습니다.
좋아.
음, 여기에 우리가 간다.
다섯 번째.
번호 6.
하나, 둘, 셋, 넷, 다섯, 여섯, 일곱.
아,이 어색한이다.
>> 스피커 2 : 난 그냥을 얻을 것이다 -.
>> DAVID J. 마란 : 좋은 거래.
좋아.
참여에 감사드립니다.
>> [박수]
>> 확인을 클릭합니다.
좋아.
그래서 우리는 4, 둘, 여섯이 1, 3, 일곱, 다섯.
우리는 일곱 자원 봉사자가 너무 완벽 여기에 폭에 해당 누구
우리가 연주하는 배열 이전에.
그리고 나는 이유 일곱 선택 그 것입니다 단지
약간의 편리.
그리고 내가 먼저 제안거야 그 우리는이 일곱 자원 봉사자를 정렬합니다.
당신이 먼저 좋아 한 경우 하지만 안녕하세요. 대답
이 될 것입니다 때문에, 어색한 몇 분 거리에 있습니다.
자신을 소개합니다.
>> GRACE : 안녕하세요, 그레이스 해요.
나는 Leverett 하우스 2 학년.
>> BRANSON : 안녕하세요.
나는 브랜슨 해요.
나는 용접에 신입생 해요.
>> 게이브 : 안녕하세요.
나는 게이브 해요.
나는 캐벗 주니어 해요.
>> NEIL : 나는 닐 해요.
나는 매튜의 신입생 해요.
>> 제이슨 : 제이슨 해요.
나는 리노에서 신입생 해요.
>> MIKE : 나는 마이크 해요.
나는 회색의 신입생 해요.
>> JESS : 나는 제스 해요.
나는 Leverett 2 학년이야.
>> DAVID J. 마란 : 우수.
좋아.
글쎄, 우리의 모든 감사 지금까지 여기에 자원 봉사자.
손의 도전은 이제 것입니다 이 녀석의 정렬 될 수 있지만 다음하기
우리는 조금 생각해야 할 것입니다 얼마나 효율적으로 우리가 실제로에 대한 하드
그들을 분류.
그럼 먼저이 시도 할 수 있습니다.
너희들은 서로의 번호를 볼 수 있습니다 다만 구석의 주위에 배치하여.
가서 몇 초 정도 걸릴하고, 일종의 작은에서의 간단한
오른쪽에 큰 왼쪽.
이동합니다.
>> 확인을 클릭합니다.
좋아요.
그건 정말 이놈 빨랐다.
지금 여기에 누군가 알고리즘은 무엇 이었습니까 이 녀석이 적용된?
>> 스피커 1 : 최대 최소한.
>> DAVID J. 마란 : OK.
가장 최소한 정말로 일종의 목표,하지만 난 그 확실하지 않다
정말 알고리즘입니다.
가장 최소한 말할되지 않습니다 저를 어떻게 단계별로.
그래?
>> 스피커 1 : [들림]
>> DAVID J. 마란 : OK.
당신은보다 사람이 작은 볼 그렇다면 전화 번호는, 다음으로 이동
그들의 권리가 있습니다.
그래서 지금은 더 표현 점점 더 많은 알고리즘처럼, 당신 때문에
그 다음,이 경우 말할 수 있습니다.
그래서 우리는 어떤 종류의가 조건부 구조.
그리고이 녀석은 몇 가지 작업을 수행 할 듯 시간, 당신 중 일부는 조금 움직 때문에
거리.
그래서 아마도 어떤 종류의가 발생했습니다 그들의 마음에서 일어나는 반복.
>> 그러나 공식화하려고하자.
너희들은 다시 리셋 할 수 있다면 이 배열합니다.
우리는이를 공식화 할 수없는 경우하자 참조 비트, 다음 질문을 그냥
이 얼마나 효율적입니까?
물론, 우리는 더 천천히이 작업을 수행 할 때, 그것의로 기분 좋게 것
알고리즘 만 보자 우리가 할 수있는 경우 정확한 단계에 우리의 손가락을 넣어.
>> 그래서 두 사람은 네와 두 가지입니다.
또는 올바른 또는 잘못된 순서?
분명히 잘못된.
그래서 우리는 교체.
지금은 옆으로 이동하는거야 여기 네 여섯 말.
당신은 올바른 있거나 잘못입니까?
>> 게이브 : 수정.
>> DAVID J. 마란 : 수정.
여섯 하나?
아니.
교환하십시오.
그래서 두 스왑입니다.
여섯 세?
아니.
교환하십시오.
6-7?
좋아 보인다.
일곱 다섯?
>> JESS [들림]
>> DAVID J. 마란 : OK, 교환.
및 분류.
좋아.
그래서 분명하지, 그렇지?
그래서 더 거기에 가고 있었다.
그러나, 실제로,이 녀석도 그냥 본능적으로.
이동 있었다.
그들은 단지 한 번 멈추지 않았다 그들이 한 가지 문제가 수정되었습니다.
따라서.
사실, 내가 가진거야 같은 일을 수행합니다.
나는 되감기 다시 일종의해야 할거야 이 문제의 시작,
또는이 배열의 시작 사람들은 그들을 호출 시작하자.
>> 지금 무엇을해야 내 알고리즘 두 번째 패스에있을?
>> 스피커 1 : 같은 것.
>> DAVID J. 마란 : 같은 것.
그리고는 금방 좋아지기 시작 했어?
당신은 자신이 일을 찾을 수 자마자 같은 일 또 다시,의
더 많은 알고리즘처럼되고 덜 인간의 본능.
>> 그래서 지금, 여기에 우리가 다시 간다.
둘, 네?
아니오.
네 하나?
아, 일부는 실제로 있었다 할 수 여전히 작동합니다.
에 대한 세?
좋아요.
4-6?
여섯 살?
6-7?
OK, 이제 다.
OK, 아니.
나는 돌아 가야한다.
>> 그래서 지금, 다시, 우리는이 일을하고 좀 더 신중하게.
그리고 지금, 하나의 뇌가있다 이 알고리즘을 실행.
하나의 CPU, 당신이 경우에.
그리고 솔직히, 그 유일한 자원의 우리에 액세스 할 겁니다.
그리고 일단 우리가 키보드로 돌아 가야합니까 우리에 C와 같은 뭔가를
폐기, 우리는 프로그램을 작성하는 즉, 한 번에 한 가지 작업을 수행 할 수 있습니다.
순간 전이 녀석, 반면, 우리 활용 그들의 집단 브레인
너희들은 주 제로 그랬던 것처럼.
그래서이 일을 계속하자.
>> 두 하나.
두 세.
셋, 넷.
4, 5.
다섯 여섯.
6-7.
완료?
그래서 나는, 그러나 저 놀자 악마의 옹호.
이렇게 I, 컴퓨터의 종류 사람 단지 이 배열을 통과했다
사람들은, 내가 다 했어 그거 알아?
>> 스피커 : 1 호
>> DAVID J. 마란 : 왜?
나는 무엇을 순서대로 수행해야합니다 I이 수행하고있는 단호하게 결론?
아마 한 번 더 통과.
오른쪽?
때문에 그 이전부터 알고 모든 패스는 내가 실수를 수정하는 것입니다.
그 의미는, 어쩌면 거기 또 다른 실수
내가 수정해야합니다.
그래서 나는 단지 감기에 의해 확인 될 수 다음 검사, 1-2, 2,
셋, 셋, 넷, 4, 5, 다섯 여섯, 여섯 일곱.
OK, 지금은 어떤 일을하지 않았다.
>> 특히 내가 더를했던 기억이 없다 , 변수 같은 작업을
int를 좋아한다.
그것은 스왑 호출하고 스왑 I 번 0 인 경우 여기에 도착하고, 그 다음에, 0에서 시작
난 그냥 계속하는 어리석은 것 앞뒤로 다시 확인하고,
다시, 다시, 오른쪽?
당신은 몇 가지에 박히 때문에 무한 루프의 종류.
0 스왑, 거기에 따라서 자마자 우리는이 주장 할 수
알고리즘은 참으로 완료됩니다.
>> 자, 이것에 이름을 올려 놓을 수 있습니다.
난 그냥 우리가 제안하는 알고리즘 거품이라는 것을이 구현 되
의미 등으로 알려진 종류, 그 큰 종류입니다 수
정상까지 거품 그들의 방법을, 또는 최대 숫자의 배열의 끝에.
하지만이 알고리즘은 얼마나 효율적입니까?
나는 육체적으로 얼마나 많은 단계 있었나요 이러한 정렬, 예를 들어, 수행
일곱 사람?
>> 4 ~ 5 개?
OK, 너무 많은 궁극적으로 해답이 될 것.
하지만 그렇다하더라도, 특정한 수 너무 재미없는 것입니다.
의가 N으로 일반화 할 수 있습니다.
여기 사람들을 N, 그리고 그들이 있었다면 그래서 에서 임의의 순서, 정렬,이었다
그 원래의 순서대로 시작.
글쎄, 얼마나 많은 단계를 내가 있었나요 첫 번째 패스에 걸릴?
그것은 하나, 둘, 셋, 넷, 다섯 살 이렇게 여섯, 그들은 일곱 사람들이야,
그 여섯 일곱의 - N의 있도록 뺀 처음 단계를 반복합니다.
>> 지금, 얼마나 많은 단계를 내가 있었나요 내가 되 감아 때 수행 할?
음, 우리는 실제로 두 수있는 경우 우리가 정말하고 싶어하지만 지금은, 난
다만, 모든 권리를 말하는 것 다른 N - 1.
그래서 N 1을 뺀 얻을 것입니다 을 추적하는 성가신, 그래서 보자
단지 약간 올림.
그래서 2N 단계.
그래서 14 단계 주거나 가라.
>> 나는 얼마나 많은 시간이 걸릴 않았다 단계 다음 시간은?
음, 3N이다.
정말.
그리고 지금, 최악의 경우에 대한 예, 얼마나 많은 시간 나는 것
앞뒤로, 앞뒤로 사라 스와핑이 알고리즘을 실행
각 패스에 사람들이 대략?
그것은 실제로 오른쪽 제곱 보군?
>> 최악의 경우, 당신은 어떤 수 있기 때문에 직관적으로 생각의,
조금을하더라도 안으로 침몰하는 시간 좀
최악의 경우, 어떤 것이 칠명이에처럼 보였다
배열의 측면 해당 번호?
완전히 거꾸로, 오른쪽?
그냥, 그렇게 시뮬레이션 이름이 뭐였더라?
>> 마이크 : 마이크.
>> DAVID J. 마란 : 마이크?
OK, 마이크, 당신은 저를 통해 가입 할 수 있습니다 여기에 단지 하나의 초?
사실, 아니.
죄송합니다, 마이크하자 되감기.
이름이 뭐였더라?
>> NEIL : 닐.
>> DAVID J. 마란 : 닐.
OK, 닐, 당신은 함께 나, 당신이 괜찮다면.
그래서 난 그냥 위해 제시하는거야 단순, 그 닐은 자신에 지금있다
최악의 케이스.
하지만 구현 방법에 대해 리콜 내 알고리즘입니다.
나는 비교 비교 비교 해요 오, 비교, 비교.
지금이 사람은 밖으로있다 순서, 그래서 수정합니다.
그래서 너희들은 교환하십시오.
그러나 얼마나 멀리, 지금 고려 닐 가야합니까?
그것은 대략 보군.
당신도 알다시피, 그것은 실제로 n을 아니에요.
그것은 같은 N - 1,하지만 난 받고 있어요 약간의 짜증을 추적
번호, 그럼 그냥 n이 호출 할 수 있습니다.
>> 닐은 최대로 한 단계 각 이동 그렇다면 시간, 닐 한 단계 이동합니다,
나는이 정말 지루한 패스를 확인해야합니다 앞뒤로,이 약입니다
이 일을, N 단계 N 배의 총 그것은 나를 걸릴 것 때문
여러 단계 닐 모두를 얻을 수있는 그가 속한 곳으로가는 길.
다른 사람은 말할 것도 당신들 경우 뿐만 아니라 모든 잘못 주문했다.
>> 그럼 거품 정렬 N 제곱를 호출 할 수 있습니다.
이 알고리즘의 실행 시간, 이 알고리즘의 성능
이 알고리즘의 효율성, 우리는 단지 더 서술해야한다
n은 네모 일반적으로.
내가 할 수 있기 때문에 어느, 좋은 팔명, 아홉과 같은 예제
사람 만 명, 그 대답은 변경하지 않을 것입니다.
>> 너희들이 상관 없어, 그래서 만약하자 당신이 시작 위치로 재설정합니다.
그리고하자 다른 두 가지 방법을 시도하고 우리는 근본적으로 할 수 있는지 확인
이보다 더.
이 시간 그래서, 내가 제안하는거야 다른 알고리즘의 일종.
즉, 마지막으로 우리의 매우 영리 그리고 너희들을 가지고 옳았다
다만 어떤 종류의 권리 본능 쌍을 스왑.
하지만 난 정말이 접근하기를 원한다면 단순히 내 목표는 이동하는 것입니다
작은 숫자 모두이 방법과 그 큰 숫자를 모두 밀어
방법, 왜 난 그냥에 해당하지 않는다 대부분의 방법은 가능한 순진하고 볼 경우, I
무슨보다 더 할 수 매우 복잡한 알고리즘을?
>> 그럼 보자.
네 아주 작은 숫자입니다, 그래서 난 이 순간 당신을 떠나려고.
우, 두 번째는 더 나은 것입니다.
그래서 그냥 앞으로 단계를 수 순간?
이것은 현재 내 작은 번호가 후보, 내가 기억하는거야
그 변수 좋아 함께.
그러나 나는 계속 확인하겠습니다.
그 누군가가 번호가 작을?
여섯, 아니.
아, 다시 닐있다.
>> 그래서 난 당신을 다시 밀어거야 일종의 개념의.
닐 앞으로 올 것이다.
그리고 지금, 나는에 변수를 사용 해요 작은있는 사람을 추적
번호를 포함하도록 업데이트됩니다 닐의 위치.
음, 어디 보자.
세, 일곱, 다섯.
좋아, 내가 닐 작은 있었는지.
가장 간단한 것은 무엇입니까 내가 지금 할 수 있습니까?
난 그냥으로 내 시간을 낭비하지 않을 것이다 왼쪽 닐 한 자리를 버블 링.
왜 그냥 닐 두지 않는다 그가 어디에 속 어느 곳 물론입니까?
>> 처음에 모든 방법.
닐, 그래서 나와 함께.
그리고 당신 이름이 뭐 랬지?
>> GRACE : 그레이스.
>> DAVID J. 마란 : 그레이스.
확인을 클릭합니다.
그레이스 그래서, 불행하게도, 당신이있어 방법의 종류입니다.
그렇다면 우리는 어떻게이 문제를 해결합니까?
오른쪽?
이 배열 인 경우, 거기에 맥도널드 위치.
롭과 그 리콜, 우리는 이야기 나이를 선언하고, 우리는했다
나이의 유한 수?
여기에 같은 생각.
우리는 단지 정수의 유한 수 있습니다.
은혜는 우리의 종류의 수 있습니다 방법으로, 우리는 어떻게 문제를 해결합니까?
>> 가장 간단한 방법은 같다 은혜, 죄송합니다.
당신이 가서해야 할 것입니다 그래서 우리는 방을 거기에 만들 수 있습니다.
지금, 당신은 아마 이것에 대해 생각하면 우리는 단지 문제를 더 악화했다.
그리고 어쩌면 우리가 무슨 짓을하는 경우 때문에 은총은 바로 이곳에 있었다?
그러나 우리는 그녀가 있기 때문에, 아니 알고 그렇지 않으면, 그녀는했을 것이다
앞으로 서 대신 이 시간에 닐, 오른쪽?
우리는 이미 그녀의 수를 체크 아웃.
>> 좋아.
이제, 닐은 바로 이곳에서, 그리고 나는 약간의 최적화를 수행 할 수 있습니다.
다음 순간을 위해, 나는 무시하는거야 되지 않도록하기 위해 함께 닐 모든
자신의 시간을 낭비하거나 실수 잘못된 장소에 그를 교체하십시오.
그래서 지금, 내가 어떻게 다음을 찾을 수 있습니까 최소의 요소?
두.
경우 즉, 꽤 좋은 번호의 당신은 앞으로 족답하고 싶​​어
나는 당신을 기억합니다.
여섯, 아니 좋은.
네, 세, 일곱, 다섯, 아니 좋은.
그래서 당신은에 저를 이동할 수 오른쪽 장소입니다.
그리고 우리는 그냥이 시간 운 얻었다.
>> 지금, 나는이 무시하는거야 두 사람, 이제 하나 더 많은 일을 할
이 통과한다.
여섯, 그 아주 작은 숫자입니다.
앞으로 가자.
아, 죄송합니다.
그레이스의 숫자가 더 낫다 그래서 앞으로의 단계.
네.
죄송합니다, 그레이스.
다시 이동합니다.
세 번째는 더 낫다.
일곱.
다섯.
지금 당신의 이름을 다시 무엇인가?
>> 제이슨 : 제이슨.
>> DAVID J. 마란 : 제이슨.
그래서 제이슨은 이제 가장 작은 요소 내가 선택한.
그는 어디로 가고거야?
어디 여섯입니다.
그리고 당신의 이름은 또 무엇입니까?
>> 게이브 : 게이브.
>> DAVID J. 마란 : 게이브.
게이브 방법입니다.
할 수있는 가장 쉬운 일이 무엇입니까?
이 두 사람을 교체하고 계속합니다.
그래서 지금 보자.
누가 작은입니까?
네.
나 속임수, 그냥하자.
다섯 작은 될 것입니다.
당신이 단계 싶으면, 다음 찾기 앞으로 내가 함께 무엇을해야합니까
게이브와이 녀석?
다시 교환하십시오.
그래서 지금, 여전히 약간 순서가.
나는 게이브 그래서 작은 것으로 발견 나는 그를 튀어 너희들을 통해 이동합니다.
그리고 다.
>> 그래서 대답은 동일합니다.
최종 결과는 동일합니다.
이 두 알고리즘 중 어느 더 나은 무엇입니까?
두 번째는, 내가 들었다.
왜?
>> 스피커 3 : 그것은 단계 [INAUDIBLE]를 보군.
>> DAVID J. 마란 : 그것은 대부분의 N 단계이다.
흥미 롭군요.
그래서 비록입니까?
그래서 내가 어떻게 찾았어요 작은 요소?
얼마나 많은 단계를 내가 가지고 가야 않았다 작은 요소를 찾을?
나는 모든 방법을보고했다 끝에서 오른쪽?
그 최악의 경우, 무엇 때문에 닐은 여기 있다면?
그래서 그냥 작은 요소를 찾아 나 N 단계, 또는 n에서 1을 뺀 걸립니다.
하지만, 확인을 클릭합니다.
그래서 닐 고정합니다.
, 1 분 정도 전 그 기억.
>> 그러나 어떻게 나는 다음을 찾았어요 작은 요소?
그것은 N - 1, 또는 n 마이너스 정말 2의 단계의 수에서.
그래서 확인을 클릭합니다.
그래서 나는이 마이너스 n을했다.
좋아.
그래서 조금 더 나은 느낌.
좋아.
다음 번에 ​​얼마나 많은 단계 세 번째를 찾는 방법은?
그래서 N 마이너스 4.
그래서 1 이하로 감소하는 것 각 반복에 단계.
그래서 바로 더 나은 기분이?
마지막 경우는 약 n 번 N 있었다 이번에는 N - 1, 플러스 N 마이너스의
2, 플러스 N 마이너스 3 플러스 N 마이너스 4, 점, 점, 점.
하지만 당신은 고등학교를 호출하는 경우 교과서, 약간의 속임수
수식을 가지고 뒤에 시트, 경우 당신은 숫자의이 시리즈를 추가
단계의 총 개수는 무엇입니까 여기 걸릴 예정?
>> 이것은 그 중 하나, 좋아, n은 마이너스 1, 2로 나눈 시간 없음.
그래서 내가 해낼 수 있다면 어디 보자 잠시이 업.
그리고 또, 내가 라운딩 종류의 일부 해요 숫자는 단지 우리의 생활을 간단하게하기 위해
하지만 내 기억으로는, 그것은 경우처럼 뭔가 그 다음, n은 1을 뺀 작업을 수행 N 마이너스
2, 다음 N 마이너스 3, 그것은 대략의 2를 통해이 같은, 그리고 만약 내가
이것을 곱, 그게 실제로 N 광장.
그것도 좋은 느낌 아니에요. 2에 N을 뺀 없음.
>> 그러나 여기 것입니다.
컴퓨터 과학, 문제 n을 때 흥미로운 얻을 시작이다
정말 큰 가져옵니다.
의 n은 정말 커질 때, 그 이러한 값은 모두를 지배하는 것입니다
다른 사람?
그것은 바로, 제곱 N의 일종인가요?
예, 2로 나누어 것은 아주 좋은 것입니다.
하지만 당신은 수십억에 대해 얘기하는 경우 데이터의 조각, 또는 수조
데이터의 조각, 그래, 당신은 두 배 빠르다.
하지만 누가 정말 그 큰 숫자면 걱정 이 요인은 얻는 것입니다 경우
커지고.
확실하게, 그것은 더 있습니다 이 사람보다 차이.
너희들이 맞아 그렇게하더라도, 두 번째 알고리즘, 우리는 그것을 전화 할게
선택 정렬, 현실 세계에서,이다 빠른 비트 잠재적으로, 내가 있기 때문에
복용 줄어들고 각 시간 단계를 반복합니다.
>> 정말 근본적으로 빠른 아니다.
때문에 우리는 실제로이를 연주하면 끝의 N 큰 값
일, 충분히 큰 n에, 그것은 여전히 매우 느린 느낄 것.
음, 저를 보자 그 마침내 전달합니다.
그게 내가 부를 것이다 무엇 선택 정렬.
너희들은 스스로를 재설정 할 수 있습니다 마지막으로 한 번 더?
이 마지막 경우는거야 뭔가를 제안하기
삽입 정렬을했다.
삽입 정렬이되고, 개념, 조금 다른.
>> 앞뒤로가는 것이 아니라 작은 요소를 선택 해요
다만 이들의 각각을 다루는 것 내가 그들을 발생하고, 삽입 할 사람
그들 자신의 올바른 위치에.
그래서 난 그냥, 그레이스 시작하는거야 그리고 그녀가 네 번째의 것을 볼 수 있습니다.
네 번째는 어디에 속합니까?
나는 무엇을 정렬 시작하지 않은 그래서 그레이스는 바로 거기에 숙박을 가져옵니다.
당신은 수 있다면 지금은 항거야 이, 오른쪽에 조치를 취할
내 정렬 된 목록이 내입니다 분류되지 않은 나머지 목록입니다.
그래서 지금 난 다음에 진행하겠습니다 당신의 이름이 뭐였더라?
>> BRANSON 브랜슨.
>> DAVID J. 마란 : 브랜슨.
그래서 브랜슨 두 번째이다.
그래서 내가 당신을 데려 갈거야 순간을 위해 밖으로.
그리고 지금, 당신은 어디에 속하십니까 이 배열?
그래서 은혜의 오른쪽에.
그래서 다시 우리가 만드는 친절 그레이스는 여기에서 많은 작업을 수행합니다.
우리는 당신을 어디에 배치해야합니까?
그래서 우리는 당신을 밀어거야 왼쪽, 거기 브랜슨를 삽입합니다.
하지만 지금은 주장하는 너희들이 완료됩니다.
하지만, 통지, 나는 여분의 공간을 사용하지 않을거야.
그것은 여전히​​ 2 요소의 여기, 여기 5.
전체 배열의 크기는 7이다, 그래서 난 모든 권리, 부정 행위하지?
>> 그래서 지금 우리는 여기에 게이브로,이 6 번, 당신은 어디에 속하십니까?
다시 운이 좋았어요.
그래서 당신은 거기 숙박을 얻는다.
그냥 오른쪽으로 약간의 조치를 취할 당신이 정렬하는 것을 명확하게한다.
그리고 지금 우리는 다시 번호 닐이 한, 당신은 어디로 가야합니까?
우리가 볼 수 시작합니다 어디 지금은 하지만 처음에이 알고리즘,
눈이 꽤 똑똑한 느낌의 시계 일어날 대해거야.
당신은 앞으로 단계를 수 있다면.
>> 우리는 어디 닐를 넣어 하시겠습니까?
그래서 분명히 여기에 어떻게 우리가 닐을받을 수 있나요?
이 단계 - 의해 - 단계를 수행하자.
당신이 갈 필요 게이브?
네, 그래서 하나의 큰 걸음 또는 두 개의 반 단계를 만들려면
거기에 한 단계.
당신이 가서 은혜?
좋아요.
또 다른 단계 그래서.
그리고 마지막으로, 브랜슨?
다른 단계.
그리고 지금 우리 자리에 닐을 넣을 수 있습니다.
>> 그래서 지금,이 논리를 계속합니다.
우리는 닐를 이동하지 않더라도 이상과 이상, 그리고 그 이상을 넣어
그는 최악의 경우,가는 곳, 우리는 발생할 수있는 다음 번호 수
숫자, 말, 수 있었다 제로, 우리는 모두 이동하는 것입니다
이 녀석.
숫자, 음수가 있다고 가정 하나, 우리는 변화해야
이 사람의.
그래서 우리는 정말 내리고, 그냥있어 우리가있어되도록 주변의 문제
에서 비용을 전송 선정 과정 때문에 삽입
너희들은 그냥 가지고 그런 과정 대략 N 마이너스 뭔가를 이동합니다
단계의 수.
그리고 단계의 수는 것입니다 좀 더 번호를 선택으로 높이려면,
난 너희들을 밀어 유지해야하는 경우 다시, 다시, 다시.
>> 그래서 슬픈 것은 지금이 모든 것입니다 알고리즘은 제곱 n을합니다.
자, 가서 감사에에 사람, 이러한 비트를 시각화
다른.
아주 잘 했어.
>> [박수]
>> 좋아.
거기 당신은 간다.
주셔서 감사합니다 -
>> BRANSON : [들림] 숫자를 유지합니다.
>> DAVID J. 마란 : 아니, 당신은 할 수있다 뿐만 아니라 숫자를 유지합니다.
좋아.
잘 했어.
좋아.
그래서 우리는 지금 요약 할 수없는 경우 보자 더 빨리, 그리고 더 시각적으로,
정확히 방금 무슨 일이 일어난 여기서 다음과 같습니다.
내가 먼저 갈거야 파이어 폭스를 당깁니다.
우리는이 데모를 연결합니다 과정의 웹 사이트에.
자바는 작업을 진행하게 조금 성가신 일부 브라우저 요즘합니다.
당신은 집에서 놀 않는 경우에, 당신이 파이어 폭스를 사용할 필요가 있습니다 실현
이 작업을 얻을 수 있습니다.
그리고 내가이 함께 할거야 데모는 다음과 같습니다.
>> 아래에, 나는의 전체 무리가 시작과 등의 메뉴 옵션
버튼을 중지합니다.
또한, 옆으로,있을 것 같습니다 이 프로그램의 버그, 당신이 그것에
실제로 시작을 참조하거나 중지 할 수 없습니다 당신은 명령 또는 Alt를 누른 버튼 않는
플러스와 확대, 호기심 당신에게 더 많은 버튼이 표시됩니다.
당신이 연주하면, 그래서 그냥 FYI 이 집에서.
지금은 단지에서 시작을 클릭거야 순간의 지연을 지정한 후,
여기에 200 밀리 초 같은 단지 그래서 우리는 어떻게 볼 수 있습니다.
>> 그래서 나는이 시각화 주장 첫 번째 알고리즘의
이 녀석은 버블 정렬, 그것에, 한 우리는 사람들이 짝을 스왑.
이 시각화에 대한 통찰력 즉 막대의 높이
숫자의 크기를 나타냅니다.
키가 막대하므로, 큰 숫자입니다.
짧은 막대, 숫자 작은.
당신이 알 경우에, 우리는을거야 이 알고리즘의 첫 번째 반복,
그래서, 큰 및 작은 숫자를 교환 작은 숫자가 먼저 온다
큰 숫자는 오른쪽으로 이동합니다.
>> 그리고 곧 우리가 배열의 끝을 받으면 일곱보다 더 많은 숫자, 우리는거야
처음으로 되돌아 갈 예정.
그리고이 예상된다.
맨 왼쪽에, 그 작은 녀석이야 옆으로 스왑이하는
과정을 반복.
이제 시각화를 신속하게 얻을 수 지루한, 그럼 내가 가서 멈추게
그것은 많은 지연 무언가를 변경 빠른 다만, 지금에 대한 느낌을 얻을 수
이 알고리즘.
>> 나는 그것을 가속화했다 그래서 비록이는 구매, 내 프로세서를 업그레이드 같은
새 컴퓨터.
나는 근본적으로 변경되지 않은 내 알고리즘,하지만 당신은 실제로 더 많은 것을 볼 수 있습니다
분명히 인간보다 그 큰 숫자는 정상까지 버블 링
그리고 작은 숫자가 버블 링 아래로 아래로.
그리고 지금이 일을 여기에 분류.
그리고 옆으로, 사각형, 거기에 거기에 그냥 부기
당신은 얼마나 많은 비교를 계산하는 데 도움이 또는 얼마나 많은 스왑이
실제로 완료되었습니다.
>> 음, 중 하나를 해보자 다른 사람 우리는 보았다.
내가 여기서 버블 정렬을 클릭시키고, 나를 선택할 수 있습니다,이 전체 웹 페이지
약간의 버그입니다.
의는 위험을 감수하자 하고 다시 실행합니다.
거기 우리는 간다.
그래서 선택 정렬을 수행하자.
나도 몰라 왜 메뉴 거기가 나타납니다.
이 문제를 해결하려면의 확대하자 버그, 50로 변경.
아, 실제로하자 훨씬 더 빨리합니다.
다섯 밀리 초 정도하고 시작합니다.
>> 그래서 이것은 선택 일종이다.
그래서 다시 우리에 대해 생각 여기에 인간을 위로했다.
우리는 배열을 통해 가서 선택 다시 작은 요소
다시, 다시.
지금 나는 아직도 꽤 나쁘다고 주장한다.
그것은 여전히​​ 제곱 n을했다, 포기하거나 걸릴 하지만 조금 현실 세계에서,이었다
빨리, 내가 실제로 가지고 있었기 때문에 각 시간 단계 약간 적은.
그러나 우리는 무엇을 말하는 건가요?
여기에 아마 40 정도 바?
우리는 40 만 달러 얘기가 아니에요.
그래서 완전히 나에게 명확하지 않다 그 실제로 상당한 이득이었다.
>> 나 이제 돌아가 우리를 변경할 수 있습니다 선택 된 세 번째 알고리즘
삽입 정렬.
지금은 정말 버그 왜냐하면 메뉴가 정말 거기해서는 안됩니다.
그래서 지금 우리가 여기까지 뒤로 스크롤합니다 이 알고리즘을 시작합니다.
웁 시작 및 중지합니다.
그래서이 한 종류가 꽤 패턴이 그것, 그것에 의하여 우리는 다시이야
인간을 삽입, 또는에 이 경우 막대에
적절한 위치입니다.
그리고 그것은 이전에 이미 끝났어 나는 주위를 돌았 다.
하지만이 하나도 이론, 아직 제곱 n입니다.
>> 그래서 우리는 요약 할 수없는 경우 보자 이러한 다음과 같습니다.
내가 먼저 가서 그냥주는거야 이야기의 일반적인 방법의 우리 종류
이러한 것들에 대한, 나를 소개하자 여기에 표기 단지 조금.
당신이 뭔가 큰이라고 볼 것입니다 O, 그것은 그대로이기 때문에 큰
O. 그리고 그 컴퓨터 방법 과학자 또는 심지어는 사용하는 수학자
실행 시간을 설명하는 어떤 알고리즘.
실제로 얼마나 많은 조치를 취해야합니까?
>> 지금은 나 자신을 난처하게 할거야 여기서 잠시 내 필기.
그러나 내가 가서 그 말을하자 이 여기에 큰 O 될 것입니다.
그리고 내가 다른 하나를 소개하겠습니다 기호, 자본 오메가.
오메가는 그 반대가 될 것입니다 기본적으로, 큰 O 반면 큰 O.의
수단, 최악의 경우, 얼마나 많은 시간이 어떤 알고리즘에 걸릴 수 있습니다
N 약관, 오메가가는 얼마나 많은 시간이 수도 수
최상의 경우에 걸릴.
그리고 우리는 우리가 무엇을 의미하는 볼 수 있습니다 잠시 최고의 케이스.
>> 그래서 뭔가 간단한 시작하자.
나 선형 검색을 시작하자.
그래서 정렬되지 않습니다.
우리는이 선형 검색을 호출 할 수 있습니다.
그리고 지금, 약간을 이 표 중.
그리고 지금, 선형 검색의 경우, 최악의 경우, 얼마나 많은 단계입니다
그것은을 찾아 내게 걸릴 것 임의 선택의 수?
그리고 N 전체 문이있다 또는 n 총 숫자.
최악의 경우.
몇 단계 나에해야 할 것입니다 배열에 숫자 50을 찾기 위해 수행
n 개의 문?
왜?
그것은 모든 수 있으므로 끝에 통해 방법입니다.
제니퍼가 발생 순전히처럼, 숫자 50는, 그래서 모든 방법을 통해이었다
최악의 경우 선형 검색 N의 큰 O, 우리는 말할 것입니다.
>> 무엇 최선의 사건에 대해, 당신은 정말 운이 있다면?
그것은 단지 하나의 조치를 취할 것 단계 또는 상수.
그래서 우리는 1과 그 설명 할 것이다.
그래서 이것은 아주 좋은 것입니다.
이제 우리는 무엇인가 무엇을 한 경우 이진 검색을 좋아해?
최악의 그래서 이진 검색, , 케이스를했다 얼마나 많은 시간?
>> [목소리를 개재]
>> DAVID J. 마란 : 그래서 실제로, I 몇 장소에 들었다.
그래서 사실, N를 기록 주거나 가지고 간다 우리가 반으로 목록을 분할로 인해
다시, 다시, 다시, 우리는 할 수있어 궁극적으로 찾으려면 값
거기, 그러나 캐치가됩니다.
우리가해야하는 가정은 무엇입니까 이진 검색에 대한 당연한?
그것은 정렬 할 수 있습니다.
그것은 분류 아니에요, 당신은 일을 분할 할 수 있습니다 에서 또 다시 반하고,
왼쪽으로 갈 수 있습니다, 당신은 바로 갈 수 있고, 당신은 왼쪽과 오른쪽 갈 수 있습니다,하지만 당신은거야
요소의 경우를 발견하지 않을 목록이 정렬되지 않습니다, 때문에
당신은 그것을 놓칠 수 있습니다.
귀하의 휴리스틱 때문에, 왼쪽 가기를 위해 또는 오른쪽으로는의 경우 결함이 될 것입니다
참으로 정렬되지 않습니다.
그래서 숨겨진 비용의 종류가있다 이런 식으로 뭔가를 사용합니다.
>> 지금, 우리의 정렬에 가자 알고리즘은 검색되지 않습니다 -
아, 사실의이 공백을 가자.
최상의 경우 이진 검색?
그냥 일어나는 경우도 1의 매우 배열의 중간에, 또는에
전화 번호부의 중간.
이제 버블 정렬을 수행하자.
그래서 다시, 지금 우리는을 입력하고 종류가 아닌 검색합니다.
>> 최악의 경우, 얼마나 많은 단계 한 우리 청구 버블 정렬은 걸릴 거예요?
N 제곱.
그래서 나는 그를 그릴거야.
오, 내 필기도 더 본다 그것은 그렇게 큰 투영 일 때.
좋아.
그래서이 제곱 보군.
거품 정렬의 가장 좋은 경우에, 얼마나 많은 단계는 걸릴 것입니다?
1 들었어요.
>> 스피커 1 : N.
>> DAVID J. 마란 : N, 나는 들었다.
>> 스피커 1 : 2.
>> DAVID J. 마란 : 2 들었어요.
나는 3 들리는가?
좋아.
그래서 N, 2, 1을 들었지만, 선택하자 그 중 떨어져 적어도 첫 번째
제안 1.
그것은 때문에 나쁜 본능이 아니다 종류는 여기에 패턴을 따릅니다.
그러나 그것은 단지 방법 1 단계, 소요되는 경우 세상은 내가 주장 수있는 목록
내가에만 허용 거라면 때문에 정렬 1 단계에서 얼마나 많은 요소를 가지고하는
사실은 확실하게 확인할 수 있을까?
음, 그냥 1, 그 n은 있다는 뜻 - 1 요소 즉, 수 중 수
순서, 그리고 난 후 바로 믿음거야 1 요소를 찾고 그
것은 정렬됩니다.
여기에 해결 안 1 그래서.
그래서 최소한 얼마나 많은 나는보고해야합니까?
>> [목소리를 개재]
>> 정말 N - 1, 또는 : DAVID J. 마란 N, I마다보고해야하기 때문에
이 있는지 확인하기 위해 요소 그것은 순서가 아니다.
그러나 다시, 우리는 파 우리의 정렬됩니다 작은 숫자에서 손
n은 대형수록, 그들이있어, 가정 어쨌든 재미.
그래서 거품 정렬입니다.
그리고 지금, 마지막 두 작업을 수행하자.
다음 선택 정렬, 우리는거야 삽입 정렬을 수행합니다.
그리고 우리는 당신을 날려 버릴 것입니다 많은 뭔가 마음
이 모든 것보다 더 나은.
좋아.
>> 실행하는 최악의 경우는 무엇입니까 선택 정렬의 시간은?
>> 스피커 4 : N 제곱.
>> DAVID J. 마란 : 해당 사각형, 내가 듣고 있어요.
그런데 왜 여기서 n은 직관적 제곱?
>> 스피커 4 : 우리가 해냈어 때문입니다.
>> DAVID J. 마란 : 우리가 해냈어 때문입니다.
확인을 클릭합니다.
좋은 대답.
하지만 직관적으로, 왜 선택입니다 종류의 N 제곱?
우리는 무엇을 했는가 또 다시?
우리는을 통해 스캔을 계속했다 당신 작은, 당신은있다
작은, 당신은 작은 수 있습니다.
그리고 부여, 우리는 N을 수 있었다 단, 다음 N 그 - 1, n은 마이너스 2.
하지만 당신이 어떤 종류의 사람 모두를 추가 할 경우, 아니면 내가 추가 한 믿음을 가지고
사전에 그들까지, 우리는 N 대략받을 일부 작은 숫자 마이너스 제곱.
그래서이 N 제곱 호출하는거야.
그러나 가장의 선택 종류로 경우, 그것은 얼마나 많은 단계입니다
저를 데려 갈?
>> 스피커 5 : [들림]
>> DAVID J. 마란 : 그것은 불행의 아직 N 제곱, 오른쪽?
나는 작은을 선택하는 거라면 때문에, 요소, 우리는 여기에 칠명을했다
난 단지 알고, 일단 난 아주에 도착 끝이 나는 작은 발견했습니다
번호, 어디 그 또는 그녀는되었을 수도 있습니다.
그러나 어떻게 나는 다음을 찾을 수 있습니까 작은 숫자?
또 다른 패스를 할 수 있습니다.
그래서 최선의 경우, 무엇인가 선택 정렬에 입력?
그것은 이미 정렬 목록에서 번호를 하나의 두 번째, 세 번째, 네 번째.
하지만 컴퓨터를 해요.
나는 단지 한 곳에서 볼 수 당시의 것.
걸음의 I는 정렬 할 수 없습니다 다시 인간과 말과 같이,
우,이 올바른 보인다.
>> 난 단지의 정확성을 판정 할 수 을 선택하여 선택 정렬
작은 숫자.
그러나 나는 번호 하나가 처음 발견하더라도, 나는에 대해 아무것도 모르는 경우
내가 모르는 다른 숫자, 모든 I 내가 배열을 넘겨 봤는데 알고
어느 뒤에 문 또는 집합 번호, 나는 그 하나를 알고있는 유일한 방법은
작은인가?
여기 모든 방법을 실현하는 경우, 젠장, 하나는 실제로 작은 하였다.
>> 하지만 어떻게 그 다음을 확인합니까 두 사람은 다음으로 작은입니까?
같은 비 효율성을 수행하여 또 다시.
그래서 결국, 삽입 정렬과 함께, 방법, 최악의 경우,
우리가 수행하는 말 했는가?
그것은 너무 제곱 n입니다.
및 방법에 대한 최상의 경우가 있나요?
우리는 클리프 행어로하는을 남겨 둘 것이다.
우리는 그 빈 다음을 입력합니다 하지만 먼저 내가 제안하자 그 우리
근본적으로보다 나은 이 모든, 모든 권리?
>> 그래서 자신에 대한 생각을 삽입 정렬거야.
글쎄, 그건 매우 극적인 아니었다 나는 유일한 사람 때문에
그 변화를 보았다.
와우.
확인을 클릭합니다.
그래서 여기에 우리가 다소있다 다른 데모.
여기에서 확대하면, 당신은을에 볼 수 있습니다 왼쪽 우리에서 거품 종류가
우리는 선택의 종류가 중간, 및에 오른쪽, 우리는 무언가가 우리
아직 못 봤어 정렬을 병합했다.
그러나 우리가 도움이되었다고 한 것을 고려 오늘 지금까지 여기서 뭐.
제니퍼 처음 무대에 올라 왔을 때, 우리는 숫자의 배열을 통해 갔다
다시, 다시, 선형 검색과 함께, 우리는 큰 O, 선형 실행 시간을 가지고
N으로, 말하자면.
>> 우리는 지금의 첫째 주를 고려할 때 클래스, 우리는 분열과 정복했을 때,
우리는 전화 번호부, 찢어했다 제니퍼, 우리 총칭
에 있었다 활용할 해당 키 통찰력, 에 의해 또 다시 자신을 반복
어떻게 든, 멀리 던지기, 멀리 던지기 멀리 던지는 문제의 절반 또는
일반적으로, 절반에 문제가 나누어, 다음의 작은 조각을 치료
개념 동등 문제 다른, 우리는 어떻게 든 한
근본적으로 더 나은.
그러나 버블 정렬과 함께 선택 정렬 삽입 정렬과 함께, 우리는했습니다 수도
제니퍼했던 그런 통찰력 없습니다.
우리는 꽤 많은 단지 뒤로 걸어 등 전체 시간의 무리, 그리고 우리
불통 상황이 조금 스와핑 이 순서에서, 어쩌면
삽입하거나 선택.
하지만 하루의 끝에, 내가 많이했다 어색하게 걷고 앞뒤로.
우리가 정말 활용 뭔가하지 않았다 제니퍼와 같은 스마트 나누는 좋아했다
그리고 정복.
>> 그래서 정렬을 병합 대조적으로, 이는 우리 다음 주까지 표시되지 않습니다, 그것은거야
활용 나누어 해당 키 아이디어 입력 한 다음, 절반, 그리고
절반, 그리고 절반.
그리고 그 루프의 각 반복에, 왼쪽 절반을 정렬하고 오른쪽
반, 왼쪽 절반의 왼쪽 반 후, 다음 왼쪽과 오른쪽 절반,
왼쪽 오른쪽 절반의 절반, 그리고 오른쪽 절반의 오른쪽 절반.
그리고 또 다시 반복.
>> 그래서 당신은 시각이 표시되지만이 있습니다 다음 주에 우리를 기다리고 것입니다.
그리고 일반적으로 때, 우리는 조금 생각 이러한 문제에 조금 더.
우리는 왼쪽에 제곱 N, N있다 중간에 제곱, 그리고 N
오른쪽에 N를 기록합니다.
그래서 실제 클리프 행어가있다.
우리는 월요일에 당신을 볼 수 있습니다.
>> [박수]