DAVID 마란 : 좋습니다. 우리는 다시 수 있습니다. 프로그래밍에이 분야에 그래서 나는 우리가 사물의 혼합이다 할 거라고 생각했다. 하나는 조금 할 뭔가 손에, 더 장난을 사용하여이기는하지만 프로그래밍 environment-- 의 실증 하나 아이디어 정확히 종류 우리는 얘기를했습니다 하지만 좀 더 공식적으로. 두, 일부 봐 더 기술적 인 방법 프로그래머 실제로 해결한다고 탐색 문제 같은 문제 우리가 전에에서 본과 또한보다 근본적으로 정렬의 흥미로운 문제. 

우리는 그냥 가서 얻을에서 가정 그 전화 번호부가 분류되었다, 하지만 혼자가 실제로 종류의 여러 가지 방법으로 어려운 문제 그것을 해결합니다. 그래서 우리는 이러한를 사용합니다 문제 클래스 사물의 대표가 일반적으로 해결 될 수 있습니다. 그리고 우리는 얘기하자 몇 가지 세부 사항에 대한 내용 데이터라고 structures-- 연결리스트와 같은 애호가 방법 및 해시 테이블과 나무 그 프로그래머 실제로 것 사용 일반적으로 사용 화이트 보드에 페인트 의 사진 그가 또는 그녀 구현하기위한 구상 소프트웨어의 일부 조각. 

그럼 제 1 부분에 손 - 더 할 수 있습니다. 그래서 그냥 더러운 손을 얻을 환경이라고 scratch.mit.edu. 이것은 우리가 사용하는 도구입니다 우리 학부 클래스입니다. 그것은 설계에도 불구하고 12 세까지를위한, 우리는 위쪽을 위해 사용 그 아주 조금의 일부 그것은 좋은 재미 이후 학습의 그래픽 방법 프로그래밍에 대한 작은 선물. 그래서 어디를 그 URL에 머리 확실히이 같은 페이지가 표시됩니다, 그리고 가서 클릭 오른쪽 상단에 스크래치 가입 및 사용자 이름과 선택 암호 궁극적으로 자신을 얻을 account-- scratch.mit.edu. 나는 내가로 사용할 것이라고 생각합니다 기회는 먼저이를 표시합니다. 질문은 휴식 시간 중 등장 무엇에 대한 코드는 실제로처럼 보인다. 그리고 우리가 얘기했다 C에 대한 휴식 시간 중, 에 particular-- 특히 이전 언어로 낮은 수준. 그리고 난 그냥 빨리했다 구글 C 코드를 찾기 위해 검색 이진 검색 알고리즘에 대한 그 우리 일찍 전화 번호부를 검색하는 데 사용됩니다. 이 특별한 예, 물론, 전화 번호부를 검색하지 않습니다. 그것은 단지의 전체 무리를 검색 컴퓨터 메모리의 숫자. 하지만 당신은 단지 시각을 얻을하려는 경우 어떤 실제 프로그래밍의 의미 , 보이는 것처럼 언어 보인다 이 같은 작은 선물. 그래서, 약 20 플러스의 코드의 30 정도 선, 그러나 대화 우리 휴식 시간 동안 가지고 있었던 어떻게이 사실에 있었다 0과 1로 변신됩니다 당신은 단지 그것을 되돌릴 수없는 경우 처리하고 0과 1로 이동 코드에 백업합니다. 

불행하게도, 공정 이렇게 변형입니다 그것은 훨씬 쉽게 있다고 말하기는. 내가 나서서 실제로 설정 그 프로그램, 이진 검색, (A)의 방법에 의해 0과 1로 프로그램은 컴파일러를 호출하는 I 내 Mac에서 바로 여기가하는 일. 그리고 당신은 화면을 보면 여기에 특별히 초점을 맞추고 이 가운데 여섯 컬럼 만, 당신은 단지 0과 1을 볼 수 있습니다. 그리고 그는 0과 1이다 그 정확하게 검색 프로그램을 구성한다. 

그리고 5 비트의 각 청크, 여기에 0과 1의 각 바이트, 일부 명령을 나타냅니다 일반적으로 컴퓨터의 내부. 그리고 사실, 당신이 들었어요 경우 마케팅 슬로건 "인텔 인사이드"- 즉, 물론, 당신은이 의미 컴퓨터 내부의 인텔 CPU 또는 뇌. 그리고는 CPU가된다는 것이 무엇을 의미하는지 당신은 명령어 세트를 가지고, 말하자면. 

많은 세계의 모든 CPU, 그들에게이 일 인텔에 의해, 유한 이해 지침의 수입니다. 그리고 그 명령은 매우 낮은 수준이다 으로는,이 두 번호를 추가 이 두 숫자를 곱하면, 여기에서 데이터의이 조각을 이동 여기에 메모리에이를 저장 여기에서 정보는 메모리에 여기까지 그래서 forth-- 때문에 매우 낮은 수준의 거의 전자 세부 사항. 하지만 그 수학적으로 작업 결합 우리는 앞에서 설명한 것과, 데이터의 표현 수 0과 같은 당신은 모든 것을 구축 컴퓨터가 있는지, 오늘 할 수있는 그것은, 텍스트, 그래픽, 음악의 또는 그렇지 않으면. 

그래서이 얻을 매우 쉽습니다 신속의 잡초에 잃었다. 그리고 많은있다 구문 도전 이에는 간단한 할 경우, 프로그램의 오타 없음의 멍청한 무엇이든지 작동합니다. 그래서 대신를 사용하여 C와 같은 언어 오늘 아침, 나는 것이라고 생각 더 재미있는 사실은해야 할 일 시각적 뭔가하는 아이들을위한 설계하면서 완벽한 표현은 실제로 실제 프로그래밍 language-- 단지에 발생 텍스트 대신 이미지를 사용 그 아이디어를 나타냅니다. 

당신은 참으로이되면 그래서 scratch.mit.edu에 계정, 버튼 만들기 클릭 상단에있는 사이트의 왼쪽. 그리고 당신은 같은 환경을 볼 수 내 화면에 표시하려고 해요 하나 이리. 그리고 우리는 조금을 보내고 있습니다 시간의 비트가 여기에 재생합니다. 우리는 모두 몇 가지를 해결할 수없는 경우 보자 다음과 같은 방식으로 함께 문제. 

그래서 당신이 내 볼 수 있습니다 environment-- 실제로 그냥하자 나 일시 중지합니다. 사람이 여기 없어? 여기가 아님? 승인. 그래서 내가 몇 가지를 지적하자 이 환경의 특성. 

화면의 왼쪽 상단 그래서, 우리 스크래치의 무대를 가지고, 말하자면. 스크래치뿐만 아니라 이름입니다 이 프로그래밍 언어의; 또한 고양이의 이름의 그 당신은 오렌지가 기본적으로 참조하십시오. 그는, 무대에 너무 많은 내가 설명 등 A의 인 것으로 이전 거북이 직사각형 화이트 보드 환경을 제공합니다. 이 고양이의 세계는 완전히 한정된다 거기에 그 사각형까지 가기. 

한편, 오른쪽에 여기서 편, 그것의 그냥 스크립트 영역, 빈 슬레이트가됩니다. 이것은 우리가 쓸거야 어디 그냥 순간에 우리의 프로그램. 그리고 빌딩 블록을 우리가하여야한다 이 퍼즐을 program-- 작성하는 데 사용할 조각, 당신이 will-- 경우 중간에 바로 여기, 그들은 분류하고 기능에 의해. 그래서, 예를 들어, 내가 가서거야 이들 중 적어도 하나를 보여준다. 내가 가서 클릭거야 맨 위로 제어 범주. 

그래서이 최고 최대 범주입니다. 나는 컨트롤 범주를 클릭거야. 오히려, 나는 이벤트를 클릭거야 카테고리, 맨 처음 일까지 최고. 그리고 당신도 함께 수행하려는 경우 우리가 이렇게, 당신은 아주 환영합니다. 나는 클릭하고이를 끌어 갈거야 첫 번째, "녹색 깃발을 클릭." 그리고 난 그냥 드롭거야 대략 내 빈 슬레이트의 상단에. 

그리고 스크래치에 대한 좋은거야 인이 퍼즐 조각, 때 다른 퍼즐과 연동 조각, 문자 그대로 할 것입니다 그 퍼즐 조각은 할 말. 그래서, 예를 들어, 스크래치가 맞다 지금 자신의 세계의 중간에있다. 내가 가서 선택하는거야 지금의 말을하자, 모션 카테고리, 당신은 작업을 수행하려는 경우 모션 카테고리를 똑같이,. 그리고 지금은 전체가 알 여기에 퍼즐 조각의 무리 다시 종류의 할 것을 그들이 무슨 말을. 내가 가서 끌어거야 바로 여기 이동 블록을 놓습니다. 

그리고 그 즉시 당신이 얻을로 주목 은 "녹색 깃발의 바닥에 근접 클릭 "버튼 예고 방법 흰색 선이 나타납니다, 거의 비록로 자기, 거기 가고 싶어. 그냥 가자, 그리고 스냅됩니다 함께와 모양이 일치합니다. 그리고 지금 당신이 할 수있는, 아마도 거의 우리가 함께가는 곳 같아요. 

당신은 스크래치 단계에서 보면 여기에 그것을의 상단에 보면, 당신은 붉은 빛을 볼 수하는 기호 및 녹색 깃발을 중지합니다. 그리고 앞서 갈거야 내 screen--를보고 단지 순간을 위해, 당신이 할 수있는 경우. 난을 클릭거야 지금 깃발을 녹색, 그는 10 단계로 보이는 이동 또는 화면에 10 픽셀, 10 점. 

그리고 그 흥분하지, 하지만 내가 제안하자 심지어이 교육없이 바로 자신의 intuition--하자 자신을 사용하여 나 당신이 방법을 알아낼 것을 제안한다 바로 단계 떨어져 스크래치 산책을합니다. 그를의 오른쪽위한 방법을 만들기 적이 화면 오른쪽 끝까지. 내가 당신에게 잠시 시간을 줘 보자 정도 그와 씨름합니다. 당신이보고 싶을 수도 블록의 다른 카테고리에서. 괜찮아. 그래서 그냥 우리가있을 때, 요약하자면 녹색 깃발은 여기를 클릭 10 단계를입니다 이동 전용 명령어마다 I 녹색 깃발을 클릭, 무슨 일이야? 글쎄, 내 프로그램을 실행합니다. 그래서 나는이 작업을 수행 할 수 아마 수동으로 10 배, 그러나 이것은 조금 느낌 비트 hackish 때문에, 말하자면 이에 정말 아니에요 과제를 해결하기. 난 그냥 다시 노력하고있어 및 다시 또 다시 때까지 나는 종류의 실수 지시문을 달성 것을 나는 이전에 달성하기 위해 밖으로 설정합니다. 

그러나 우리는 알고 우리의 의사 이전이 있다고 루프의 프로그램에서이 개념, 또 다시 일을하고. 그리고 내가 본 당신의 무리 어떤 퍼즐 조각을 위해 도달? 때까지 반복합니다. 그래서 우리는 뭔가를 할 수 같은 때까지 반복합니다. 그리고 당신은 정확히까지 무엇을 반복 했습니까? 

승인. 그리고 나에게있어 하나 가자 단지 잠시 동안 다소 간단합니다. 내가 가서이 작업을 수행 할 수 있습니다. 당신이 가진 수 있으므로, 그 주목 컨트롤에서 발견, 이 반복 블록은 존재하는 그것처럼 보이지 않는 것은이 크다. 에하지 여지가있다 그 두 개의 노란색 선 사이. 그러나로 당신의 일부는있을 수 있습니다 드래그 앤 드롭하면, 발견, 이 모양을 채우기 위해 성장하는 방법을 알 수 있습니다. 

그리고 당신은 더 많은 벼락 공부 할 수 있습니다. 그냥 경우 성장하겠습니다 당신은 드래그하고 위에 마우스를 올려. 그리고 나는 무엇을 모른다 여기에 가장 좋은, 그래서하자 나 이상에 대해 5 회 반복 인스턴스는 다음 단계로 돌아가 및 녹색 깃발을 클릭합니다. 그리고 지금은 꽤가 아니라 알 수 있습니다. 

이제 여러분 중 일부는 다음과 같이 제안 빅토리아는 10 번 반복했다. 그리고 일반적으로 수행 모든 방법을 잡을, 하지만 거기하고자하면보다 강력한 될 임의의 파악보다 훨씬 얼마나 많은 움직임을 만들어? 무엇이 더 나은 블록 수 있습니다 반복보다 10 배는 될? 

그래, 왜 영원히 뭔가를하지? 그리고 지금 내가이 퍼즐 조각을 이동하자 이 안에이 하나 제거. 지금 어디 스크래치없이 통지 시작, 그는 가장자리로 이동합니다. 그리고 다행히도 MIT, 누가 그냥 스크래치를 만든다 확실히 그는 그 절대하지 않습니다 완전히 사라집니다. 당신은 항상 자신의 꼬리를 잡을 수 있습니다. 

그리고 바로 직관적으로, 왜 그는 계속 움직이고 있습니까? 무슨 일이야? 그는 중지 한 것으로 보이지만 나는 드래그를 선택 후 경우 그는 거기 가고 싶은 유지합니다. 그 이유는 무엇입니까? 정말, 컴퓨터는 그대로입니다 당신이 그것을 말해 무엇을 할 것. 당신이 그것을 말했다 그래서 만약 이전을 영원히 일을 다음, 10 단계를 이동, 가서 계속 것 나는 붉은 정지 신호를 칠 때까지 그리고 모두 프로그램을 중지합니다. 

당신은하지 않았다 그래서 경우에도 이렇게, 어떻게 내가 할 수 빠른 스크래치 이동을 화면에서? 더 많은 단계, 오른쪽? 그래서 그 대신 10 일을 한 번에, 왜 우리는하지 않습니다 가서 그것을 건 ... 변경 당신은 (50)은 무엇 propose-- 것인가? 그래서 지금은 녹색을 클릭거야 플래그는, 실제로, 그는 정말 빨리 간다. 

물론 이것은 그냥 애니메이션의 표현. 애니메이션은 무엇입니까? 그것은 단지 당신에게 인간의을 보여주는 것 정말 정지 영상의 전체 무리, 정말, 정말 빨라요. 그리고 그래서 만약 우리가 그냥 말하는 거 그에게 더 많은 단계를 이동, 우리는 단지 효과가있을 데있어 그 화면에 변화 시간을 더욱 빠르게 당 단위. 

내가 제안 이제 다음 도전 그 가장자리를 반송해야하는 것이 었습니다. 그리고 무엇 퍼즐 모르고 그것을 잘 때문에 조각 exist-- 당신은에 도착하지 않는 경우 challenge--의 단계 무엇을 당신은 직관적으로 수행 할 수 있습니까? 어떻게 우리가 그를 다시 반송해야하고 항 좌우 사이? 

네. 그래서 우리는 어떤 종류의 필요 조건, 그리고 우리 에, 그래서 조건문을 갖고있는 것 같다 컨트롤 범주, 말한다. 이들 블록 중 우리는 아마 하시겠습니까? 그래, 어쩌면 "만약, 그럼." 그래서 노란색 블록 사이에 그 통지 우리는이 "만일"이 여기에있다 또는이 "만약, 다른"방어 것 우리 이렇게 결정을 내릴 수 있도록 또는 그렇게 할 수 있습니다. 그리고 당신이 할 수도 둥지를 여러 일을 할 수 있습니다. 아니면 아직 여기 사라없는 한 경우, 감지 범주에 가서 그리고 -이 여기에 있는지 보자. 

그래서 블록 여기에 도움이 될 수 있습니다 그가 단계 떨어져 있는지 감지하는 방법? 그래,이 블록의 일부를 알 매개 변수화 될 수있다, 말하자면. 그들은 일종의 아니라 사용자 정의 할 수 있습니다 HTML과는 달리 어제 속성, 어디 그 속성의 종류 태그의 동작을 사용자 정의 할 수 있습니다. 마찬가지로 여기,이 감동을 잡을 수 있습니다 블록과 변화와 질문을, 당신은 마우스를 건드리지있다 커서와 같은 포인터 또는 당신은 가장자리를 만지고있다? 

그래서 내가 가서이 작업을 수행 할 수 있습니다. 나는 잠시 축소거야. 날이 퍼즐 조각을 잡아 보자 여기,이 퍼즐 조각이, 나는 뒤범벅거야 단지 잠시 동안 그들입니다. 나는이 이동거야 감동 가장자리로 변경, 이렇게 나는 운동에 갈거야. 그래서 여기에 몇 가지 성분입니다. 나는 내가 원하는 모든 것을 가지고 생각합니다. 

누군가가 방법을 제안 하시겠습니까 I 이 아마 위에서 아래로 연결할 수 있습니다 갖는 문제를 해결하기 위해서 스크래치 이동에 왼쪽에서 오른쪽으로 오른쪽 각 왼쪽으로 왼쪽에서 오른쪽으로 시간은 벽 떨어져 튀는? 내가 뭘 할 수 있습니까? 어떤 블록 내가 연결해야 "녹색 깃발 먼저 클릭"? 

OK, 그래서이 시작하자 "영원히." 무엇 다음 내부 간다? 다른 사람. 확인 단계를 이동합니다. 괜찮아. 그리고 뭐? 그래서 다음 경우. 그리고 보이는 경우에도 통지 단단히 함께 샌드위치, 그냥 채우기 위해 성장할 것입니다. 그것은 단지 내가 원하는 위치로 이동합니다. 

그리고 사이에 무엇을 넣을까요 는 IF와 다음? 아마 "경우 가장자리를 터치." 통지는, 다시, 너무 크다 그것을 위해,하지만 채우기 위해 성장할 것입니다. 그리고 15도 회전? 몇도? 그래, 그래서 (180)는 회전합니다 내 주위 모든 방법. 그래서이 권리를 가지고 있는지 알아 보자. 나 축소 할 수 있습니다. 

나 스크래치까지 드래그 할 수 있습니다. 그래서 그는 왜곡 약간의 지금,하지만 괜찮아요. 어떻게 쉽게 그를 다시 할 수 있습니까? 나는 약간 속이려고하고있다. 그래서 다른 추가 해요 블록은 단지 명확합니다. 나는 그 90도를 가리 키도록 할 기본적으로 오른쪽으로, 그래서 난 그냥 그에게거야 프로그래밍 방식으로 그렇게 할 수 있습니다. 그리고 여기 우리는 간다. 우리는 그것을 한 것 같다. 이 때문에, 조금 이상한 그는 거꾸로 걸어. 의 버그 있음을 부르 자. 그건 실수. 버그 프로그램,의 실수 I, 인간이 만든 논리 오류가 발생했습니다. 왜 거꾸로거야? MIT는 망치 또는 I을했다나요? 

그래, 내 말은, 그것은 MIT의 아니에요 결점. 그들은 나에게 퍼즐 조각을했다 그 정도의 어떤 수를 설정했다. 그리고 빅토리아의 제안에, 나는 180도 회전하고있어, 이는 바로 직관이다. 그러나 사실상 180도 선회 180 ° 회전 수단 그것은 정말 아니다 내가 원하는, 분명히. 적어도 그가에있어 때문에 이 2 차원의 세계, 그래서 터닝 정말 가고 거꾸로 그를 플립합니다. 

아마 어떤 블록을 사용하려면 당신이 여기에서 무엇을 볼 대신에, 기초? 우리는 어떻게이 해결할 수 있습니까? 그래, 그래서 우리는 지점 수 반대 방향이다. 그리고 실제로 심지어이다 충분히 될 수 없습니다, 우리는 하드 코드 할 수 있기 때문에 왼쪽이나 오른쪽을 가리키는 것이다. 

당신은 우리가 무엇을 할 수 있는지 알아? 우리는이 것 같습니다 여기에 편의를 블록. 내가 확대 할 경우, 참조 뭔가 우리가 여기 좋아? MIT는이 같은 그것은 본다 추상화는 여기에 내장. 이 블록은 동등한 것으로 보인다 다른 블록, 복수하는에? 

이 하나의 블록은 동등한 것으로 보인다 블록이 전체의 트리오에 것을 우리는 여기에 있습니다. 이 밝혀 그래서 나는 단순화 할 수 있습니다 내 이 모든 치우는에 의해 프로그램 바로 여기에 넣고. 그리고 지금 그는 여전히 약간의 버그, 그리고 지금은 괜찮습니다. 우리는이 떠날 것입니다. 하지만 내 프로그램은 짝수 간단하게,이 역시 대표적인 것 programming--의 목표 이상적으로 코드를 확인하는 것입니다 간단한 가능한 분체, 여전히 같이하면서 가능한 읽을. 당신은 너무 간결하게하고 싶지 않아 이 어려운 것을 이해합니다. 

하지만 교체 한 알 하나 세 블록, 그것은 틀림없이 좋은 일이다. 나는 개념을 멀리 추상화 한 의 당신이있어 여부를 확인 한 블록 가장자리에. 이제 우리는 사실이 재미를 가질 수 있습니다. 이것은 너무 많이 추가하지 않습니다 지적 값하지만 장난 값입니다. 나는 앞서 갈거야 여기에이 소리를 잡아. 그래서 내가 가서 보자, 나를 보자 잠시 프로그램을 중지합니다. 나는 다음을 기록하는거야, 내 마이크에 대한 액세스를 허용한다. 

여기에서 우리는 간다. 아야. 이제 다시 해보자. 여기에서 우리는 간다. OK, 나는 잘못된 일을 기록했다. 여기에서 우리는 간다. 아야. 아야. 괜찮아. 지금은 그 제거해야합니다. 괜찮아. 

그래서 지금 내가 가지고 단지의 기록 "아야." 지금 그래서 내가 갈거야 앞서이 "아야."전화 나는 돌아갈거야 내 스크립트, 그리고 지금 통지라고이 블록이있다 사운드 "야옹"을 재생하거나 사운드를 재생 "아야." 나는이 끌어 가고, 어디 있어요 나는 코믹 효과를 위해이를 넣어해야합니까? 그래, 그래서 지금은 가지입니다 버그가 있기 때문에 지금이 block-- 알 방법이 "가장자리에있는 경우, 바운스는 "급식의 일종이다. 그래서이 문제를 해결해야합니다. 내가 가서이 작업을 수행 할 수 있습니다. 날이 없애 보자 돌아가 우리의 원래의,보다 신중한 기능을 제공합니다. "가장자리를 터치하면 다음"그래서 내가 원하는 빅토리아는 제안으로, 회전하기, 180도. 그리고 내가 놀고 싶어 할 이 "아야"소리? 

그래, 외부의 알 그 노란색 블록. 이 때문에, 너무 될 것 버그,하지만 난 그것을 나타났습니다. 그래서 여기에 그것을 끌어거야, 통지 지금은 내부의 "만약." 은 "만약"그래서 이런 종류입니다 같은 암 같은 오의 그는 것 그 안에 무엇이 않습니다. 그래서 지금은에서 축소하는 경우 annoying--의 위험 

컴퓨터 : 아야, 아야, 아야. 

DAVID 마란 : 그리고 그냥 영원히 갈 것입니다. 지금은 단지 물건을 가속 여기, 내가 가서 열어 보자, 의 날 일부에 가자 say--하자 클래스 내 자신의 물건. 그리고 이제,이 말을하자, 나를 열어 보자 하나는 우리의 교육 동료 중 하나에 의해 만들어진 몇 년 전에. 그래서 일부는 기억 수도 있습니다 작년부터이 게임, 그것은 놀라운 사실이다. 우리가 한 경우에도 지금은 프로그램의 간단한, 의 어떤이를 생각해 보자 실제로처럼 보인다. 내가 플레이를 공격 할 수 있습니다. 

그래서이 게임에서, 우리는이 개구리, 화살표를 사용하여 keys-- 그는 내가 꼭 기억해보다 더 큰 조치를 취하고 나는이 개구리 제어 할 수 있습니다. 그리고 목표는 바쁜에서 얻을 수 있습니다 자동차로 실행하지 않고 도로​​. 그리고, 내가 여기 가면의이 see--하자 I 로그가로 스크롤 할 때까지 기다릴 필요가. 이 버그 같은 느낌이 든다. 이 버그의 일종이다. 괜찮아. 나는 여기에있어 거기에, 그리고 당신은 유지 모든 얻을 때까지가는 릴리 패드에 개구리. 지금이 보일 수 있습니다 더욱 복잡한 하지만의 휴식을 시도하자 이 아래로 정신적으로 구두 및 그 구성 블록으로. 그래서 아마 퍼즐있다 우리가 아직 보지 못한 작품 하지만 키 입력에 응답하는 것, 일에 나는 키보드했다​​. 

그래서 아마 어떤 종류의있다 키가 동일한 경우는 말한다 블록, 다음 Scratch--으로 뭔가를 할 아마 10 단계 이러한 방법으로 이동합니다. 다운 키를 누르면, 10 단계 이동할 이러한 방법으로, 또는 왼쪽 키를 10 단계로 이동 이 방법 (10)은 단계. 나는 분명히 개구리에 고양이를 설정했습니다. 그래서 그냥 어디있어 스크래치 호출은 우리를 그건 ... 의상으로 그냥 개구리의 사진을 가져 왔습니다. 

하지만 무슨 일이 일어나고 그 밖의 무엇? 어떤 코드의 다른 라인, 어떤 다른 퍼즐 조각 블레이크했던, 우리의 교육 동료, 분명히,이 프로그램에 사용할 수 있습니까? 어떻게 모든 것을 만들고있어 난 그러고 어떤 프로그램 구성? 

모션, 그래서 sure-- 확실히, 블록을 이동합니다. 그리고 그 움직임 블록 무엇 , 대부분의 내부? 그래, 루프의 일종, 아마 영원히 어쩌면 반복, 차단 block-- 블록까지 반복합니다. 그리고 그 어떤 로그를 만들고있다 및 릴리 패드와 모든 다른 이동 이리저리. 그것은 단지 끝없이 일어나고. 

이유는 자동차의 일부입니다 다른 사람보다 더 빨리 이동? 해당 프로그램에 대해 다른 무엇입니까? 네, 아마 그들 중 일부는 복용 번에 단계 그들 중 일부 한 번에 적은 단계. 그리고 시각 효과 느린 대 빠릅니다. 

당신은 무슨 일이 어떻게 생각하십니까? 내가 개구리를 가지고있는 모든 방법 거리와 강을 가로 질러 백합 패드, 뭔가 상 주목할만한 일어났다. 어떻게 최대한 빨리 그처럼 일어 났는가? 이 멈췄다. 그 개구리를 중지하고, 나는 두 번째 개구리를 얻었다. 그래서 구조를해야합니다 거기에 사용, 어떤 기능이? 

그래, 그래서 어떤 종류의있다 너무, 거기 컨디셔닝 "만일". 우리는이 항아리 보지 않았다해서 돌출 그리고집니다 그러나이 점에서 다른 블록을 거기에 당신이 접촉하는 경우, 말할 수있다 화면에 다른 것, 당신은 "다음."백합 패드를 터치하는 경우 그리고 그 때 우리를이다 두 번째 개구리를 표시합니다. 그래서이 게임은 확실히 경우에도 매우 심지어 첫눈에 있지만, 일자 거기에 너무 많은 on--와 블레이크가는 2 분이 재빨리하지 않았다, 그것은 아마 그가 몇했다 시간이 게임을 만들 수 있습니다 그의 기억이나 동영상을 기반으로 그것의 왕년의 버전. 그러나 이러한 작은 것들의 모든 격리에서 화면에 가고 이러한 매우 간단합니다 아래로 비등 constructs-- 운동 또는 문 우리가 언급 한 같은, 루프 및 조건, 그리고 그것에 대해이야. 몇 가지 다른 애호가 기능이있다. 그들 중 일부는 순수하다 미적 또는 음향, 소리처럼 그냥 함께했다. 그러나 대부분의 경우, 당신 이 언어, 스크래치에있는, 기본의 모든 빌딩 블록 당신이 C, 자바, 자바 스크립트에있는, PHP, 루비, 파이썬, 다른 언어의 수. 스크래치에 대한 질문? 괜찮아. 그래서 우리는 스크래치에 깊은 다이빙하지 않습니다, 이번 주말 환영합니다 있지만, 특히 당신은 아이가있는 경우 또는 조카 등, 스크래치에 소개합니다. 실제로 훌륭하게 장난이야 환경과 그 저자가 말하는 것처럼, 매우 높은 천장. 우리는 시작하더라도 매우 낮은 수준의 세부 정보, 당신은 정말 꽤 작업을 수행 할 수 있습니다 그것으로, 이는 아마도 정확히의 데모. 

그러나의 지금은 좀 더로 전환하자 복잡한 문제, 만약에 당신, "검색"으로 알려져 있으며, 더 일반적으로 "정렬". 우리는이 전화 번호부는 earlier-- 여기에 있었다 다만 discussion-- 또 다른 하나 우리는 검색 할 수 있었다 보다 효율적으로하기 때문에 중요한 가정의. 그리고 그냥 명확하게하는 것 가정은 내가 결정했다 이 전화 번호부를 통해 검색 할 때? 마이크 스미스 있다는 전화 번호부, I 불구하고 처리 할 수​​있을 것입니다 그없이 시나리오 난 그냥 조기가 정지합니다. 이 책은 알파벳입니다. 그리고 그것은 매우 관대이야 가정, 그 때문에 나는 친절 해요 누굴 의미 코너 절단, 같은 나는 누군가 때문에 빠른 오전 다른 나를 위해 많은 노력을했다. 

그러나 만약 전화 이 책은 정렬되지 않은가요? 아마 버라이존이 게으른있어, 그냥 던져 모든 사람의 이름과 번호가에 아마 순서대로하는 그들 전화 서비스에 가입. 그리고 얼마나 많은 시간을하면 나를 걸립니까 마이크 스미스 같은 사람을 찾는 방법은? 1000 페이지의 전화가 얼마나 많은 book-- 페이지는 내가 통해보고해야합니까? 

그들 모두. 당신은 운이 일종의입니다. 당신은 말 그대로에서 모든보고있다 페이지 전화 번호부 그냥 경우 무작위로 분류. 당신은 운이 마이크를 찾을 수 있습니다 맨 처음 페이지에, 그 때문에 첫 번째 고객이었다 전화 서비스를 주문합니다. 그러나 그는 역시 마지막되었을 수 있습니다. 

따라서 임의의 순서는 좋지 않다. 그래서 우리는 정렬이 있다고 가정 전화 번호부 또는 일반 정렬 데이터 것을 우리는 주어진했습니다. 우리는 어떻게 할 수 있습니까? 

음, 나 그냥 해보자 여기에 간단한 예. 내가 앞으로 가서 던져 보자 칠판에 몇 번호. 이다 우리가 숫자를 가정 이제, 네, 둘, 하나, 3을 가정 해 봅시다. 그리고, 벤, 우리를 위해이 숫자를 정렬합니다. 

그래 좋아. 당신은 그렇게 않았다 방법? 괜찮아. 그래서 작은 시작 값이 가장 높은, 그것은 정말 좋은 직관이다. 그리고 우리를 실현 인간은 실제로 꽤 있습니다 문제 해결에 좋은 이런 식으로, 적어도 데이터가 상대적으로 작은 경우. 즉시 수백을 시작으로 숫자, 숫자의 수천, 숫자의 수백만, 벤 아마 아주 그렇게 빨리 그것을 할 수 없었다, 가 있다고 가정 숫자의 간격. 만에 카운트 아주 쉽게 그렇지 않으면, 단지 시간이 많이 소요. 

따라서 알고리즘이 들린다 벤 지금 바로 사용 등 가장 작은 번호를 검색했다. 그래서 우리 인간은 걸릴 수 있지만 시각적으로 많은 정보에, 컴퓨터는 실제로 좀 더 제한. 컴퓨터 수 있습니다 만 한 번에 한 바이트 보면 으로 ..에서 아니면 4 바이트 으로 ..에서 요즘은 아마 8 바이트 그러나 극소수 주어진 시간에 바이트. 

그래서 우리가 정말이 주어진 네 개의 개별 값 here-- 당신은 것으로 벤 생각할 수 그는 컴퓨터 등을 인 경우에 곁​​눈 가리개 그는 다른 것을 볼 수 없습니다 으로 .. 하나의 수보다 그래서 우리는 일반적으로처럼, 가정합니다 영어, 우리는 오른쪽에서 왼쪽으로 읽을 수 있습니다. 그래서 첫 번째 숫자 벤은 아마 보았다 에서 매우 빠르게 다음 네이었고, 그것은 꽤 큰의 실현 number-- 나를 계속 찾아 보자. 

두 가지가있다. 분을 기다립니다. 두 네보다 작다. 내가 기억하는거야. 두 이제 작다. 지금 one--이 더 나은입니다. 즉, 더 작은입니다. 나는 약 2를 잊어 버린거야 그리고 지금 일을 기억한다. 

그리고 그는 찾고 막을 수? 글쎄, 그는 기초 수 이 정보에, 그러나 그는 더 나은 검색을 거라고 목록의 나머지. 목록에 무엇 제로 경우했기 때문에? 어떤 하나의 제외가 목록에 있다면? 그는 단지 그의 대답 것을 알고있다 그는 철저하게인지 정확 전체 목록을 확인. 그래서 우리는 나머지 봐. 그 셋 ... 시간 낭비였다. 불운있어,하지만 난이었다 그렇게 할 올바른 여전히. 그리고 지금 그는 아마도 작은 수를 선택 그냥 처음에 넣어 목록, 나는 여기 다하겠습니다있다. 지금은 비록, 다음에 무엇을 했는가 당신은 거의 그것에 대해 생각하지 않았다 이 정도? 이 과정을 반복, 루프 그래서 어떤 종류. 친숙한 아이디어가있다. 그래서 여기에 네 가지입니다. 즉, 현재 가장 작은입니다. 즉, 후보입니다. 아니 더 이상. 지금은 두 가지를 보았다. 그 다음 가장 작은 요소입니다. 그 때문에, 작지의 셋 ... 지금 벤은 두 가지를 뽑아 수 있습니다. 

그리고 지금 우리는이 과정을 반복하고, 물론 세 다음에 꺼내됩니다. 이 과정을 반복합니다. 네 꺼내됩니다. 그리고 지금 우리가 숫자에서있어, 그래서 목록 정렬해야합니다. 

실제로,이 공식 알고리즘이다. 컴퓨터 과학자 것 "선택 정렬"이 전화 아이디어는 일종의있는 Being 다시 iteratively-- 목록 다시 다시 선택 가장 작은 수입니다. 그것이 대해 좋은거야 그것은 너무 터무니없는 직관적입니다. 너무 간단합니다. 그리고 당신은 동일한 작업을 반복 할 수 있습니다 작업을 다시하고 다시. 그것은 간단합니다. 

이 경우 빠른했지만 실제로 얼마나 걸립니까? 의 그것을 보이게하자 좀 더 지루한 느낌. 따라서 하나, 둘, 셋, 넷, 다섯 여섯 7, 8, 9, 10, 11, 12, 13, 14, 15, 16-- 임의의 숫자. 난 그냥보기를 원했다 바로 사보다 시간입니다. 그래서 전체를 가지고있는 경우 숫자의 무리를 now-- 심지어는 중요하지 않습니다 그들은하자의를으로 죠 무엇 어떤이 생각 알고리즘은 정말 좋아합니다. 

이 숫자가 가정하자. 또, 중요하지 않습니다 무슨 그들은,하지만 그들은 무작위입니다. 나는 벤의 알고리즘을 적용하고있다. 나는 가장 작은 수를 선택해야합니다. 어떻게해야합니까? 그리고 육체적에 갈거야 그것은 그것을 행동이 시간을한다. 찾고 찾고, 찾고 찾고 찾고. 단지 내가 도착 시간에 의해 리스트의 종료 할 나는 작은 실현 수는 2이 시간이었다. 하나는 목록에 없습니다. 그래서 두 사람은 내려 놔. 

나는 다음에 무엇을해야합니까? 찾고 찾고 찾고 찾고. 지금 나는 때문에, 숫자 일곱 발견 이 numbers--에 간격이있어 그러나 다만 임의. 괜찮아. 그래서 지금은 일곱을 넣을 수 있습니다. 찾고 찾고 찾고입니다. 

지금은,의 있으리라 믿고있어 물론, 벤이하는 것을하지 여분의 RAM을 가지고 추가 메모리 때문에 물론 저도 같은 번호로 찾고 있어요. 확실히 나는 기억하고 있었다 그 숫자의 모든 그것은 절대적으로 사실입니다. 그러나 벤 모든 기억 경우 숫자의 그가 본 것, 그는 정말 만든되지 않았습니다 기본적인 진행 그는 이미 가지고 있기 때문에 검색 기능 보드의 숫자를 통해. 의 모든 기억 숫자는 도움이되지 않습니다 그는 컴퓨터와 정지 할 수 있기 때문에 단지, 우리가 말한, 하나의 숫자를 보면 한번에. 그래서 속임수의 어떤 종류가 없습니다 당신은 거기 활용할 수있다. 

현실에서, 같은 그래서 목록을 검색 유지, 말 그대로 그냥 계속해야 앞뒤로 그것을 통해 밖으로 따 버릴 다음 작은 수입니다. 그리고 같은 당신이 가지 추론 할 수있다 내 어리석은 움직임에서, 이 단지 매우 도착 매우 빠르게 지루한, 내가 다시 갈 것와 앞으로, 뒤로 꽤. 지금 공정하게, 내가 갈 필요가 없습니다 확실히, 음, 공정하게 see--하자, 꽤 걸을 필요가 없습니다 많은 단계마다. 왜냐하면 물론, I 등 목록에서 번호를 선택, 나머지 목록은 짧아지고 있습니다. 

그리고의에 대해 생각해 봅시다 얼마나 많은 단계를 사실이야 각각의 시간을 통해 와가. 최초 상황에서 우리는 16 숫자를했다 등의 그냥하자 maximally-- discussion--에 대해이 작업을 수행 나는 (16)를 통해 볼 수밖에 없었습니다 숫자는 작은을 찾을 수 있습니다. 하지만 일단 내가 밖으로 뽑아 적은 수의 방법 긴 물론 나머지 목록을했다? 15. 그래서 얼마나 많은 숫자는 벤 또는 내가 가지고 있었다 주위에 두 번째 시간을 통해 찾으려면? 15, 그냥 가서 작은을 찾을 수 있습니다. 하지만 지금은, 물론, 목록이며, 또한, 그것은 이전보다 작다. 그래서 얼마나 많은 단계를 내가했다 다음에 시간이 걸릴해야? 14 다음 13 다음 12 플러스 점, 난 그냥 하나 남아있어까지 점, 점. 그래서 지금 컴퓨터 과학자는 것 모두 동일한 것이 무엇을 잘 물어? 실제로 일부 콘크리트와 동일 숫자는 우리는 확실히 할 수 산술적으로, 그러나 우리는 얘기하고 싶지 알고리즘의 효율성에 대한 더 많은 공식을 통해 (formulaically) 조금, 리스트가 얼마나 독립적. 

그리고 그거 알아? 이 16이지만, 같은 내가 전에 말했듯이, 그냥 문제의 크기를 호출하도록 n은 어떤 숫자 n을. 아마 어쩌면 그것의 16의 세, 어쩌면 백만입니다. 모르겠어요. 난 상관 없어. 내가 진정으로 원하는 것은 수식 내가 할 수있는 이 알고리즘을 비교하는 데 사용 다른 알고리즘에 대하여 누군가가 주장 수도 좋든 나쁘 있습니다. 

그래서 그것은 밝혀, 단지 I 초등학교에서이 알고, 이 사실은 같은 밖으로 작동 N을 통해 n은 일 더하기 이상 2 일. 그리고 이것은,의 동일하게 발생 과정은 플러스 N 이상 2 제곱 N. 그래서 만약 내가 수식을 원했다 얼마나 많은 단계 모든보고에 참여했다 또 다시 그 숫자의 다시 다시, 나는 말할 것 그것은 N 플러스 N 이상 2 제곱입니다. 하지만 당신은 알아? 이것은 단지 지저분 해 보인다. 난 그냥 정말 원하는 사물의 일반적인 의미. 그리고 당신은 기억 할 수 고등학교가있다 최상위 용어의 개념입니다. 이 기간 중, n 개의 상기 N, 또는 절반 제곱 시간이 지남에 가장 영향을? 더 큰 n은 얻을 수있는 대부분의 이러한 문제의? 

즉, I는 연결하면 만에, N 제곱 가장 가능성이 될 것입니다 지배 인자, 때문에 만 번 자체가 많이 크다 보다 더한 백만 추가. 그래서 당신은 무엇인지? 이 같은 이놈이 큰 숫자는 숫자를 제곱합니다. 이건 정말 문제가되지 않습니다. 우리는 십자가를 겁니다 그 아웃 그것에 대해 잊어 버려요. 그래서 컴퓨터 과학자는 말할 것 그 알고리즘의 효율성 N 정도이다 squared-- 나는 진정으로 근사치를 의미한다. 그것은 종류의 약 N 제곱된다. 시간이 지남에, 더 큰 더 큰 N이 가져옵니다 무엇에 대한 좋은 평가입니다 효율성이나 효율성의 부족 이 알고리즘의 사실이다. 내가 유도하는, 물론, 실제로 수학을하고부터. 하지만 지금은 물결 치는거야 내 손에, I 때문에 단지 이 알고리즘의 일반적인 의미 할 수 있습니다. 

그래서 동일한 로직을 사용하는 한편, 의 다른 알고리즘을 생각해 보자 우리는 이미 at-- 선형 검색을 보였다. 언제이 검색되었습니다 전화 book--에 대한 찾고이를 정렬되지 전화 book--을 통해 우리는 것을 말하고 있었다 1000 단계 또는 500 단계. 그러나 이제 그 일반화 할 수 있습니다. n 개의 페이지가 있다면 전화 번호부, 무슨 일이야 실행 시간 또는 선형 검색의 효율성? 이 순서에의 얼마나 많은 단계하면 찾을 수 있습니다 마이크 스미스 선형 검색을 사용하여 첫째 알고리즘 또는 제? 

최악의 경우, 마이크에서 책의 끝 부분이다. 전화 번호부는 1,000 페이지가 있다면, 우리는, 최악의 경우에는, 상기 전회 그것은 대략 얼마나 걸릴 수 있습니다 많은 페이지는 마이크를 찾는 방법은? 1000 등을들 수있다. 그것은 상한입니다. 그것은 최악의 상황이다. 그러나 다시, 우리는 멀리 이동하고 지금 1000과 같은 숫자에서. 그것은 단지 N입니다. 

그래서 논리적 인 결론은 무엇인가? 전화에서 마이크 찾기 n 개의 페이지가 책 아주 최악의 경우에, 걸릴 수 있습니다, 얼마나 많은 N 정도의 단계? 그리고 실제로 컴퓨터 과학자는 말할 것 실행 시간, 또는 그 성능이나 효율 알고리즘 등의 또는 비 효율성, 선형 검색 (n)의 순서입니다. 그리고 우리는 동일하게 적용 할 수 있습니다 무언가를 건너의 논리 난 그냥 초에했던 것처럼 알고리즘 우리는 전화 번호부로했다 여기서 우리는 한 번에 두 페이지를 갔다. 

그래서 1000 페이지 전화 번호부 수도 500 페이지 교대로 우리를 데려, 더하기 하나 우리는 조금 뒤로 두 번합니다. 그래서 전화 번호부 N 개의 페이지를 포함하지만 우리는 한 번에 두 페이지를하고있는 그 대략 무엇입니까? 이상 2 N, 그래서 두 가지 이상의 N 같아요. 그러나 나는 주장 a를 만든 2가 있으며 넘는 순간 전 그 N 그것은 단지 n은 같은 종류입니다. 그것은 단지 일정한 요인이다 컴퓨터 과학자들은 말할 것이다. 의 만 집중하자 변수, 정말 .. 식에서의 큰 변수. 

하나를 수행할지 여부 그래서 선형 검색, 한번에 페이지 또는 한 번에 두 개의 페이지, 일종의 근본적으로 동일하다. 그것은 N의 순서에 아직. 그러나 나는 이전에 내 사진과 함께 주장 세 번째 알고리즘은 아니었다 선의. 그것은 직선이 아니었다. 그것은 그 곡선이고, 대수 공식이 무엇입니까? N--의 로그인 그래서 N의 기본이를 기록합니다. 그리고 우리는 너무로 갈 필요가 없습니다 대수에 자세히 오늘, 하지만 대부분의 컴퓨터 과학자는 않을 것 심지어 기본이 무엇을 알려줍니다. 이 때문에 모든 단지 상수 요인 때문에, 말하자면 단지 약간의 수치 차이. 그리고 이것은 매우 일반적인 일 것 특히 형식적인 컴퓨터 방법 보드 과학자 또는 화이트 보드에 프로그래머 실제로 주장하는 그들이 사용하는 것이 알고리즘 또는 무엇 효율성 그들의 알고리즘이다. 

그리고 이것은 반드시 무언가가 아니다 당신은 어떤 훌륭한 세부 사항 논의 하지만 좋은 프로그래머는 사람이다 누가 고체, 형식적인 배경을 가지고있다. 그는 이야기 할 수 있어요 방법의이 종류에서 당신 실제로 확인 같은 질적 인수 에 이유 한 알고리즘 또는 소프트웨어의 한 조각 다른 어떤 방법으로 우수하다. 당신이 확실히 할 수 있기 때문에 한 사람의 프로그램을 실행 및 초 카운트 그것은 몇 가지 숫자를 정렬하는 데 걸리는, 당신은 몇 가지를 실행할 수 있습니다 다른 사람의 프로그램 및 수를 카운트 초의이 걸립니다. 그러나, 이는보다 일반적인 방법은 그 는 알고리즘을 분석하는 데 사용할 수있는, 단지에, 만약에 당신 종이하거나 구두로. 없이도없이 그것을 실행 짝수 샘플 입력하려고 당신은 그것을 통해 추론 할 수 있습니다. 그래서 개발자 나 경우 고용과 그를 갖는 또는 그녀는 일종의 당신에게 주장 왜 자신의 알고리즘, 자신의 비밀 수십억을 검색하기위한 소스 에 대한 웹 페이지의 사용자 회사는이 더 나은입니다 인수의 종류는 그들이 이상적으로 만들 수 있어야합니다. 아니면 적어도이 있습니다 물건의 종류 그에서, 토론에 올 것 매우 형식적인 토론에서 적어도. 괜찮아. 그래서 벤 뭔가를 제안 선택 정렬했다. 하지만이 있다고 제안거야 또한,이 일을 다른 방법. 난 정말 좋아하지 않았다 무엇 벤의 알고리즘에 대한 그가 걷고 있었다, 또는이다 나 앞뒤로 걷고, 한 앞뒤로 앞뒤로. 대신 경우 어떻게 할 것 인 무엇 여기에이 숫자 같은 것을 난 그냥 각각 처리했다 수 차례에 나는 그것을 제공하고 있습니다로? 

즉, 여기에 숫자의 내 목록입니다. 네 번, 세 개의. 그리고 난 다음을 수행하겠습니다. 나는 숫자를 삽입하는거야 그들은 오히려 속하는 경우 한 번에 하나씩 선택보다. 즉, 여기에서 네 번째이다. 

여기에 내 원래의 목록입니다. 그리고 유지하려고 해요 여기에 기본적으로 새로운 목록입니다. 그래서이 이전 목록입니다. 이 새로운 목록입니다. 나는 네 번째는 첫 번째 참조하십시오. 나의 새로운 목록은 처음에 비어 그래서 하찮게의 경우 그 네 이제 목록을 모듬된다. 난 그냥, 내가 주어진거야 수를 데려 갈거야 그리고 나는 나의 새 목록에 넣어 해요. 

이 새로운 목록 정렬되어 있습니까? 네. 한 거기 때문에 바보 소자 있지만 반드시 정렬있다. 장소 중 아무것도 없습니다. 그것은 더 흥미로운,이 알고리즘, I는 다음 단계로 이동합니다. 

지금은 일이있다. 그래서 하나 물론에 속하는 시작하거나 새 목록의 끝? 시작입니다. 그래서 나는 지금 어떤 일을해야합니다. 나는 몇 가지를 복용 한 내 마커의 자유 그냥 일을 그려서 나는 그들을 원하는 곳, 하지만 그건 정말 아니다 컴퓨터에서 정확한. 우리가 아는 한 컴퓨터는있다 RAM, 또는 랜덤 액세스 메모리, 그 하나의 바이트이고 다른 바이트 다른 바이트. 그리고 당신의 기가 바이트가있는 경우 RAM, 당신은 억 바이트를, 그러나 그들은 한 위치에 물리적으로입니다. 당신은 주위에 물건을 이동할 수 없습니다 칠판에 그려서 네가 원하는 어디든지. 나의 새로운 목록이 있다면 메모리에 4 곳, 불행하게도 네입니다 이미 잘못된 장소입니다. 

그래서 수를 삽입 한 난 그냥 여기 그릴 수 없습니다. 이 메모리 위치가 존재하지 않습니다. 즉 부정 될 것이다, 내가왔다 몇 분 동안 그림으로 부정 행위 이리. 그래서 정말, 내가 여기에 하나를 넣어하려는 경우, 나는 일시적으로 사를 복사해야 다음 거기에 1 점을 추가하는 듯. 

즉, 그것은 맞습니다, 괜찮아요 즉, 기술적으로 가능 하지만 추가 작업의 실현. 난 그냥 자리에 수를 두지 않았다. 내가 먼저 이동했다 숫자이어서, 장소에 보관 그래서 나는 종류의 작업 내 양을 두 배로. 그래서 마음에 보관하십시오. 

그러나 지금은이 요소에 끝났어요. 지금은 세 번째를 잡아 싶어요. 어디 물론, 그것은 속해 있습니까? 사이. 더 이상 속일 수 없다 단지, 거기에 넣어 또,이 때문에 메모리 물리적 위치에 있습니다. 그래서 사를 복사해야 그리고 여기에 세 가지를 넣어. 아니 큰 문제. 그것은 단지 하나 추가 단계입니다 again-- 매우 저렴 느낀다. 

하지만 지금은 두 가지로 이동합니다. 둘은 물론, 여기에 속한다. 지금 당신은 어떻게보고 시작 작업이 무더기로 쌓이기 수 있습니다. 이제 무엇을해야합니까? 그래, 난 네를 이동해야, 그때 세 가지 복사 할 지금은 두 가지를 삽입 할 수 있습니다. 그리고이와 캐치 알고리즘, 흥미롭게도, 그것은 우리가 더 극단적 있다고 가정한다 그것의 여덟, 일곱 가정 해 봅시다의 경우, 6, 5, 4, 3, 2, 하나. 이것은 많은 상황에서, 인, 최악의 경우, 이놈의 일 때문에 말 그대로 거꾸로입니다. 

정말하지 않습니다 벤의 알고리즘에 영향을 미칠 때문에 벤의 선택에 정렬 그는 계속 것 앞뒤로 목록을 것. 그리고 그는 항상 찾고 있었기 때문에 전체 나머지 목록을, 그것은 중요하지 않습니다 요소가있는 곳. 하지만 내 삽입이 경우 approach--의이 시도 할 수 있습니다. 

따라서 하나, 둘, 셋, 넷, 다섯, 여섯, 일곱, 여덟. 하나 둘 셋 넷, 다섯, 여섯, 일곱, 여덟. 나는 팔을거야 어디서 나는 그것을 배치해야합니까? 글쎄, 내 목록의 시작 부분에서, 이 새로운 목록이 정렬되어 있기 때문이다. 그리고 나는 그것을 밖으로 교차합니다. 

어디 칠을 배치해야합니까? 그것을 터무니. 그것은, 거기에 갈 필요가 그래서 나는 약간의 복사를해야한다. 이제 일곱 여기 간다. 지금은 여섯로 이동합니다. 지금은 더 많은 작품입니다. 

여덟는 여기에있다. 세븐은 여기에있다. 이제 여섯 여기에 갈 수 있습니다. 지금은 다섯을 잡아. 이제 팔 가고있다 여기에, 칠이 여기에있다, 여섯 여기에 있고, 이제 다섯 반복합니다. 그리고 나는 꽤 많이 해요 끊임없이 이동. 

그래서 결국에,이 algorithm-- 우리는거야 삽입 실제로 sort-- 호출 너무 많은 일이있다. 그냥 다르다 벤의보다 작업의 종류. 벤의 작품은 나를 가고 있었다 앞뒤로 항상, 작은 다음을 선택 요소 다시 다시. 그래서 작업이 매우 시각적 인 친절했다. 

아직이 다른 알고리즘, correct--이 작업을 얻을 것이다 done-- 단지 작업의 양을 변경합니다. 처음에 당신이있어 것 같습니다 당신은 단지이기 때문에, 저장 각 요소를 처리 앞까지의 모든 산책없이 벤과 같은 목록을하는 방식이었다. 그러나 문제는 특히 이들에서, 이 모든 이전 버전의 미친 경우, 당신은 종류의 단지 것 열심히 연기 당신은 당신의 실수를 해결하기 위해 때까지. 

그리고, 그래서 만약 당신이 상상할 수 여덟 일곱 여섯 다섯 이상 네, 셋, 둘 목록을 자신의 길을 이동, 우리가 변경 한 작업의 종류는 우리가 일을하고 있습니다. 대신에 그 일의 내 반복의 시작, 난 그냥 그것을하고 있어요 모든 반복의 끝. 그래서,이 알고리즘 밝혀 또한, 일반적으로 불리는 삽입 정렬, 제곱 N의 순서이기도하다. 그것은 더 좋은 사실은 없다 더 좋은 전혀 없습니다. 

그러나, 세 번째 방법이있다 내가 생각하는 우리를 격려 것 어떤이있다. 그래서 간단하게하기 위해, 내 목록을 가정 또, 4 개의 번, 세 단지 네 개의 숫자 2가 있으며. 벤, 좋은 직감했다 좋은 인간의 직관 전에,하는 우리는 전체를 고정 eventually-- 삽입 정렬을 나열합니다. 나는 우리를 따라 구슬려. 그러나의은을 살펴 보자 이 목록을 해결하는 간단한 방법. 

이 목록은 분류되지 않습니다. 왜? 영어, 이유를 설명 그것은 실제로 분류 아니에요. 이 분류되지 무엇을 의미 하는가? 

학생 : 그것은 순차적 아닙니다. 

DAVID 마란 : 순차적하지 않습니다. 나에게 예를 제공합니다. 

학생 : 순서에 넣어. 

DAVID 마란 : OK. 나에게 더 구체적인 예를 제공합니다. 

학생 : 순서를 오름차순. DAVID 마란 : 오름차순 없습니다. 더 정확합니다. 난 당신이 상승 무슨 뜻인지 모르겠어요. 뭐가 문제 야? 

학생 :의 가장 작은 숫자는 최초의 우주에 있지 않습니다. 

DAVID 마란 : 작은 수의 하지 첫 번째 공간입니다. 더 구체적으로. 내가 잡을 시작 했어. 우리는 계산 만하고 여기 순서가 무엇입니까? 

학생 : 수치 순서. DAVID 마란 : 수치 순서. 유지의 모든 사람의 종류 그것은 매우 높은 수준을 here--. 그냥 말 그대로 무엇을 말해 5 년 된 힘과 같은 잘못된. 

학생 : 플러스 하나. 

DAVID 마란 : 무엇입니까? 

학생 : 플러스 하나. 

데이비드 마란은 : 당신은 무엇을 더한을 의미합니까? 나에게 다른 다섯 살주세요. 잘못된, 엄마는 무엇입니까? 잘못된, 아빠는 무엇입니까? 이 정렬되지 않습니다 무엇을 의미합니까? 

학생 : 그것은 바로 이곳이 아니다. 

DAVID 마란 : 무슨 일이야 하지 않을 권리 장소에서? 

학생 : 네. DAVID 마란 : OK, 좋아. 그것이 있어야 할 곳에 따라서 네 가지가 아니다. 특히,이 권리는? 네 하나, 제 내가 보는 두 개의 숫자. 이 권리인가? 아니, 순서가있어, 오른쪽? 사실, 지금 생각 또한, 컴퓨터에 대한. 그것은 단지, 아마 한 곳에서 볼 수 있습니다 once--에서 아마 두 가지 실제로 단 한 가지 한번에 있지만 수있는 적어도 한 가지에서 다음을 보면 바로 옆에 다음 일은. 

그래서이 순서대로인가? 당연히 아니지. 그래서 당신은 무엇인지? 왜 우리는 아기를하지 않습니다 이 문제를 해결 단계 대신이 멋진 일을 벤, 같은 알고리즘 그는 일종의하여 고정이야 목록을 반복 대신, 여기서 내가 한 일을의 우리가 가서 그냥 가지를 고정? 그냥 그대로를 분해하자 order-- 숫자 순서의 개념, 당신이 원합니까 어떤 호출 이 페어의 비교에. 

네 하나. 이 올바른 순서는? 그래서 그 문제를 해결 할 수 있습니다. 하나 네, 다음 우리는 그냥 복사됩니다. 좋아, 좋아. 내가 하나 사 고정. 세 및이? 아니. 내 말은 내 손가락과 일치 할 수 있습니다. 네 세? 

그것은 순서가 아닌, 그래서 나는거야 하나, 셋, 넷, 두 가지를 할 수 있습니다. 그래 좋아. 지금 사 및이? 우리는 너무,이 문제를 해결해야합니다. 따라서 하나, 셋, 2, 4. 그래서 정렬? 아니하지만 정렬에 가까운? 

우리는이 문제를 해결하기 때문이다 실수, 우리는이 실수를 고정 우리는이 실수를 고정. 그래서 우리는 틀림없이 세 가지 실수를 고정. 아직도 정말 정렬 보이지만하지 않습니다 그것은 정렬을 객관적으로 가까운 우리는 그 실수의 일부를 고정하기 때문이다. 

지금은 다음에 무엇을해야합니까? I 일종의 목록의 끝에 도달 하였다. 내가 해결 한 듯 모든 실수 있지만. 이 경우, 어떤 숫자 때문에 가까이까지 버블 수도 다른 숫자에 해당 순서가 아직. 그럼 다시하자, 나는거야 단지 장소에서이 시간을 해. 한 세? 괜찮아. 세 및이? 물론 아니, 그래서 그것을 변경할 수 있습니다. 그래서 둘, 셋. 셋, 넷? 그리고 지금은 그냥하자 여기에 특히 현학적. 이 분류되어 있습니까? 당신 인간은이 분류 압니다. 

나는 다시 시도해야합니다. 그래서 올리비아 내가 다시 시도 제안하고있다. 왜? 컴퓨터가 없기 때문에 우리 인간의 눈의 고급 단지 back-- 확인을이기는, 난 끝났어요. 어떻게 컴퓨터가 결정 하는가 목록이 이제 정렬되어 있는지? 기계적. 

나는 통과한다 다시 한 번, 그리고 경우에만 I 나는 어떤 실수를 찾을 수 / 수하지 않습니다 다음 네, 컴퓨터로 결론, 우리가 갈 수 있어요. 그래서 하나, 둘, 둘, 셋, 셋, 넷. 지금은 확실히이 말할 수 있습니다 내가 변경하지 때문에, 분류. 지금은 버그 단지 것 어리석은 나는 경우, 컴퓨터, 다시 그 같은 질문과 대답 다른 대답을 기대. 일이 안된다. 

그리고 이제 목록이 정렬됩니다. 불행하게도, 시간을 실행 이 알고리즘은 제곱 N된다. 왜? 는 N 개의 숫자 및에 가지고 있기 때문에 최악의 경우는 n 개의 번호를 이동해야 n 배 당신이 계속해야하기 때문에 다시 확인하고 잠재적으로 수정 이 숫자. 그리고 우리는 더 많은 일을 할 수 있습니다 너무 형식적인 분석. 

그래서 이것은 우리가 촬영 한 말을 전부입니다 세 가지 다른 접근 방식, 하나 그 즉시 직관적 벤에서 박쥐 내 제안 삽입에 이것에 정렬 당신은 종류의 시력을 잃을 경우 처음에는 나무의 숲입니다. 하지만 당신은 다시 조치를 취할 경우 짜잔, 우리는 분류 개념을 수정했습니다. 그래서이는 말을 감히된다 낮은 수준 아마도 그 다른 어떤 것보다 알고리즘,하지만하자의 우리가 시각화 할 수 있는지 이러한 방법에 의해이. 

그래서 몇 가지 좋은 소프트웨어 누군가 의 다채로운 막대를 사용하여 작성 우리를 위해 다음을 수행 할 것. 이 바의 각각의 숫자를 나타낸다. 더 큰, 바 키도 커 보이죠 수, 작은 바, 수 작은. 그래서 이상적으로 우리는 멋진 피라미드를 원하는 그것은 작은 시작, 큰 얻을 경우, 그리고 그런 의미 이 바는 분류되어 있습니다. 그래서, 가서 선택하는거야 예를 들어, 벤의 알고리즘 first-- 선택 정렬. 

그리고 그것은 무엇을하고 있는지 알 수 있습니다. 그들이가 선택한 방법 이 알고리즘을 시각화 I이었다처럼이다 내 목록을 걷고, 이 프로그램은 걷고있다 번호의 목록을, 핑크 각 강조 이를 찾고 번호. 그리고 지금 일이에 대해 무엇입니까? 

가장 작은 번호가 I 또는 벤은 갑자기 발견 리스트의 시작 부분으로 이동 도착. 그리고 그들은 퇴거를 한주의 사항 거기 수, 그것은 완벽하게 괜찮아요. 나는 세부 사항의 수준에하지 않았다. 그러나 우리는 둘 필요가 어딘가에 그 번호, 그래서 우리는 단지로 이동 생성 된 열린 자리. 그래서 나는이 속도를하려고 해요 최대, 그렇지 않으면 때문에 신속 매우 지루한된다. 애니메이션이 speed-- 우리는 간다. 그래서 지금 같은 원리 I 적용하고 있지만, 이 경우, 알고리즘을 느끼기 시작할 수 있습니다 것, 또는 좀 더 명확하게 참조하십시오. 본 알고리즘의 효과를 갖는다 그 다음 최소의 요소를 선택 그래서 당신은에 시작하는거야 그 왼쪽에 진입로를 참조하십시오. 그리고 각각의 반복에, I는 제안, 그것은 좀 덜 작업을 수행합니다. 그것은 모든 길을 갈 필요가 없습니다 다시 목록의 좌단, 이미 때문에 분류되어 사람들은 알고있다. 이처럼 그래서 종류의 느낌 각 단계이더라도 가속 동일한 시간 복용. 나머지 단지 적은 단계가있다. 그리고 지금 당신은 이러한 종류의를 느낄 수있다 알고리즘은 그것의 단부를 청소 실제로 지금이 분류되어있어. 

그래서 삽입 정렬은 모든 수행합니다. 나는 배열을 다시 무작위해야합니다. 그리고 알 난 그냥 수 그것을 무작위 유지, 그리고 우리의 근사치를 얻을 수 있습니다 같은 방법, 삽입 정렬. 내가 여기에 속도를 느리게 할 수 있습니다. 이제 그 시작하자. 중지. 

의 네를 건너 뛸 수 있습니다. 우리는 거기에 갈. 그들은 배열을 무작위. 그리고 여기에 우리가 삽입 정렬을 나아갈. 놀이. 그것은 각 다루는 것납니다 그것은 바로 발생 요소, 하지만에 속하는 경우 잘못된 장소 고지 일어날 수있는 모든 작업. 우리는 더 많은 변화 유지해야 많은 요소가 공간을 확보하기 위해 하나의 위해 우리는 장소에 넣어 싶습니다. 

그래서 우리는에 초점을 맞추고있어 리스트 만의 왼쪽 끝. 우리는 심지어 우리 at-- 못 봤어주의 사항 핑크 아무것도 강조하지 않은 오른쪽으로. 우리는 상대하고 문제는 우리가 가서 그러나 우리는 많이 만들 여전히 자신을 위해 일한다. 그리고 우리는이 속도를 그렇다면 현재 완료로 이동하고, 그것은 참으로 그것에 다른 느낌이있다. 그것은 단지 왼쪽 끝 부분에 초점을 맞추고 있지만, needed--으로 좀 더 일을 스무딩 가지의 종류 이상 물건을 고정, 하지만 함께 궁극적으로 다루고 한 번에 각 요소 하나 우리가 잘 가까이 대고 할 때까지, 우리 모든이 끝날 것입니다 방법을 알고, 그래서 조금 실망 아마입니다. 

그러나 end--의 목록 spoiler-- 정렬 할 것입니다. 그럼 마지막으로 하나 살펴 보자. 우리는 지금 막 건너 뛸 수 없습니다. 우리는 거의 다 왔어. 두 사람은 가고, 이동합니다. 그리고 짜잔. 우수한. 

그래서 지금의이 마지막 일을하자, 다시 무작위 거품 정렬과 함께. 그리고 나는 그것을 천천히 특히, 여기에 주목 아래로,이를 통해 습격 유지 않습니다. 그러나 그것은 단지 페어를하게 알 로컬 솔루션 comparisons-- 종류. 그러나 곧 우리에 얻을로 핑크리스트의 말미에, 어떻게 다시 일해야하는거야? 그래,에있는 것 , 시작 그것 때문에 만 고정 페어의 실수. 그리고 아직 다른 사람을 공개했을 수 있습니다. 이 속도를 만약 그렇다면, 당신은거야 이름이 의미하는만큼, 그 참조 의 elements-- 작거나 오히려 큰 elements--은 시작 거품에 가기까지, 당신이됩니다. 그리고 작은 요소는 아래 왼쪽에 거품을 시작. 그리고 실제로, 그 가지의 뿐만 아니라 시각적 효과. 그리고이 마무리 종료됩니다 너무 매우 유사한 방식이다. 

우리는 거주 할 필요가 없습니다 이 특정 일에. 나 역시 지금을 열 수 있습니다. 몇 가지 다른 정렬 알고리즘이있다 세계에서 몇 어떤의 여기에 캡처됩니다. 특히 학습자 사람 아니다 반드시 시각적 또는 수학, 우리가 전에했던 것처럼, 우리는 할 수 또한 audially 이렇게 우리는이와 소리를 연결합니다. 그리고 그냥 재미, 여기에 몇 가지 알고리즘, 당신이있어 특히 그들 중 하나 라고 알 것 "병합 정렬." 

실제로 근본적이다 더 나은 알고리즘, 한 종류의 병합되도록 당신이 볼하려고하고있는 것, 제곱 (n)의 순서가 아닙니다. 그것은 N의 시간의 기록 순서에의 실제로 작고 따라서 인 N, 그 다른 세보다 빠르다. 그리고 다른 몇 가지있다 우리가 볼 수 바보들. 

그래서 여기에 우리는 몇 가지 소리와 함께 이동합니다. 이 때문에 다시 삽입 정렬입니다 그냥 요소를 다루는 것 그들은 와서. 이는 거품 정렬이므로있어 그들에게 한 번에 쌍을 고려. 그리고 또, 가장 큰 요소 가기까지 버블 링됩니다. 

위로 다음 선택 정렬. 이 벤의 알고리즘입니다 다시 그는 반복적으로 선택하는 것 다음 작은 요소입니다. 그리고 또, 지금 당신은 정말 그 소리를들을 수 그것은하지만 지금까지 최대 속도이야 이 갈수록를하고있어로 각 반복에서 작동합니다. 이 빠른에게 하나, 일종의 병합, 수의 클러스터를 분류하는 함께 한 다음 결합. 그래서 왼쪽 저게 ... 절반은 이미 정렬됩니다. 

지금은 오른쪽 절반을 정렬하고있어 지금은 하나로 결합하는 것입니다. 이것은라는 뭔가 "그놈 정렬." 그리고 당신은 종류의 것을 볼 수 있습니다 그것은 앞뒤로거야 조금 여기에 작품을 고정하고 그것은 새로운 일에이 진행되기 전에. 그리고 그게 다입니다. 또 다른 종류가있다 정말 학문적 목적을 위해, 소요 "바보 같은 종류"라고 데이터는 무작위로 정렬 이 분류되는 경우 다음 확인합니다. 그렇지 않은 경우, 그것은 다시 정렬을 이 분류되어있어 경우 무작위 검사, 그리고 반복하지 않을 경우. 그리고 이론, 확률 이것은 완료 하지만 시간이 꽤 후. 그것은 가장 아니에요 알고리즘의 효율적입니다. 사람들에 따라서 질문 특정 알고리즘 또는 아무것도 도, 거기에 관련? 

음, 지금 무엇을 모두 떨어져 애타게하자 이 라인은 내가 그리기 봤는데 있습니다 그리고 내가 컴퓨터를 있으리라 믿고있어 후드 아래에 수행 할 수 있습니다. 나는이 숫자의 모든 것을 주장 나는 그들이 얻을 필요가 drawing-- 유지 메모리 어딘가에 저장됩니다. 우리는 너무, 지금이 사람을 제거 얻을 것이다. 

A의 메모리 그래서 조각 그래서 RAM DIMM은 computer-- 우리는 어제, 듀얼 검색 무엇을 다음과 같습니다 module-- 인라인 메모리. 그리고이 작은 검은 칩의 각 일반적으로, 바이트의 몇 가지 숫자입니다. 그리고 금 핀은 같다 컴퓨터에 연결 와이어 및 녹색 실리콘 기판은 그냥 무슨 일이 모두 함께 모든 것을 유지합니다. 그래서이 정말 무엇을 의미합니까? 나는 종류의이 같은 그림을 그릴 경우, 의는 단순화를 위해 가정하자 이 DIMM, 이중 그 인라인 메모리 모듈 RAM 1 기가 바이트, 1 기가 바이트입니다 얼마나 많은 바이트 전체가 메모리? 1 기가 바이트는 얼마나 많은 바이트? 그 이상. 1124은 킬로 1000입니다. 메가 백만원입니다. Giga는 억이다. 

나는 거짓말을하고 있는가? 우리는 심지어 라벨을 읽을 수 있습니까? 이것은 실제로 128 기가 바이트, 그래서 더 많은입니다. 그러나 우리는이 척합니다 한 기가 바이트입니다. 뜻 그래서 억있다 나에 사용할 수있는 메모리의 바이트 8 억 비트,하지만 우리는거야 지금 바이트의 관점에서 이야기하고, 앞으로 나아가 다. 

그래서 그 의미하는 것은 이것이다 1 바이트, 이것은 또 다른 바이트, 이 다른 바이트, 우리가 정말 원하는 경우 우리가해야 구체적으로 억 작은 사각형을 그립니다. 그러나 그것은 무엇을 의미 하는가? 글쎄, 내가 단지 확대하자 이 사진에있다. 내가 뭔가를 가지고 있다면 그 보인다 이 지금처럼 그 4 바이트를합니다. 

그래서 내가 여기에 네 개의 숫자를 넣을 수 있습니다. 하나 둘 셋 넷. 아니면 내가 네 글자 나 기호를 넣을 수 있습니다. "이봐!" 바로 거기에 갈 수있다, 문자의 각 때문에, 우리는 앞에서 언급 표현 될 수 8 비트 또는 ASCII 또는 바이트와 함께. 그래서 다른 말로하면, 당신은 할 수 내부 80 억 물건을 넣어 기억이 하나의 스틱. 지금은 다시 물건을 넣어 무엇을 의미 하는가 이 같은 메모리에 백업하는 백업하는 방법? 이것은 어떤 프로그래머입니다 에 "배열을."부를 것이다 컴퓨터 프로그램, 당신은 생각하지 않는다 기본 하드웨어에 대한이, 그 자체. 것으로 당신은 자신의 생각 억 바이트 전체에 대한 액세스, 당신은 아무것도 당신이 그것으로 할 수 있습니다. 그러나 편의를 위해 그것은 일반적으로 유용 메모리 권리를 유지 이 같은 서로 옆에. 그래서이 항아리를 확대하는 경우 우리가 확실하지 않을거야 때문에 억 조금 squares--을 그리는 의이 보드가 나타내는 가정하자 이제 메모리의 스틱. 그리고 난 그냥만큼으로 그릴 거 야 내 마커는 여기에 저를주고 끝납니다. 그래서 지금 우리는 막대기를 가지고 보드의 메모리 즉이있어 하나, 둘, 셋, 넷, 다섯, 여섯, 하나, 둘, 셋, 넷, 다섯, 여섯, 그렇게 42 바이트를 seven-- 화면 전체에 메모리. 고맙습니다. 예, 산술 잘했다. 여기에 메모리 그래서 42 바이트. 그래서이 사실은 무엇을 의미합니까? 음, 컴퓨터 프로그래머 것 실제로 일반적으로 주소 등이 메모리 생각합니다. 즉, 이들 중 각자 메모리 위치, 하드웨어, 고유 한 주소가 있습니다. 

그것은 하나의 덜컹 덜컹 울리다만큼 복잡하지입니다 광장, 캠브리지, 질량., 02138. 대신에, 단지 수있다. 이 바이트 숫자 0, 이것은이다 하나,이 두 가지이며,이 세 가지이며, 이 41이다. 분을 기다립니다. 나는 잠시 전 (42)을했다 생각했다. 나는 제로 카운트 시작 그래서 실제로 맞습니다. 이제 우리는 실제로 그것을 그릴 필요가 없습니다 그리드로, 당신은 그리드로 그리면 나는 것을 실제로 생각 약간 오해의 소지가 얻을. 어떤 프로그래머는 것, 자신의 마음에, 일반적으로 생각 메모리 단지 테이프처럼로서, 마스킹 테이프의 조각 같은 그것은 단지와에 영원히 간다 또는 당신은 메모리가 부족할 때까지. 그래서 더 일반적인 방법은 그릴 그냥 메모리에 대한 생각 이 바이트 0 개, 1 개입니다 것입니다, 둘, 셋하고는 점 도트 도트. 그리고 당신도, (42) 바이트 총이 물리적으로 실제로 수도 있지만 이 같은 더 뭔가. 

지금 생각하면 그래서 메모리이 같은 단지 테이프처럼, 이것은 무엇 프로그래머 다시입니다 메모리 어레이 부를 것이다. 그리고 당신은 실제로 저장하고자 할 때 컴퓨터의 메모리에 뭔가, 당신은 일반적으로 저장하는 일을 백 - 투 - 다시 다시 - 투 - 다시 할 수 있습니다. 그래서 우리는 숫자에 대해 이야기했습니다. 그리고 싶어 할 때 문제를 해결하기 위해 같은 네 번, 세 개의, 심지어 그냥 그리기되었다하지만 숫자 만 네 번, 세 보드에 두 컴퓨터는 것 정말 메모리에이 설정이 있습니다. 

그리고 옆에 무엇을 것 컴퓨터의 메모리에 두? 음, 아무 대답이 없다. 우리는 정말 모른다. 그리고 같은 너무 오래 컴퓨터가 필요하지 않습니다, 옆에 무엇을 상관 할 필요가 없습니다 숫자로는 치료에 대한 않습니다. 그리고 이전 컴퓨터 상기 할 때 한 번에 하나의 어드레스에서 볼 수 있으며, 이 이유의 일종이다. 

아니 기록과는 달리 플레이어와 판독 헤드 단지 특정 볼 수있는 물리적 구식 레코드의 홈 한번에 마찬가지로 컴퓨터 덕분에 수 그 CPU와에 인텔 명령어 세트 누구의 명령 중 메모리에서 읽어 또는를 memory--에 저장 컴퓨터는 볼 수 으로 .. 하나의 위치에서 때때로 이들의 조합, 하지만 한 번에 정말 하나의 위치입니다. 그래서 때 우리가 뭘하고 있었 이러한 다양한 알고리즘, 난 그냥 쓰고 있지 않다 vacuum-- 네, 하나, 셋, 둘. 그 숫자는 실제로 속해 메모리의 물리적 곳. 그래서 작은 작은있다 트랜지스터 또는 어떤 종류의 밑에서 전자 후드는 이들 값을 기억. 

그리고 총에, 얼마나 많은 비트는 지금 참여, 단지 명확하게하는 방법? 그래서이 4 바이트, 또는 지금은 32 비트 총입니다. 그래서 실제로 32 제로가와 이 네 가지를 구성하는 것. 여기에 더가있다하지만, 다시 우리는 걱정하지 않는다. 

그래서 지금의 다른 물어 보자 메모리를 사용하여 질문 끝에 그 때문에 오늘의 분산이다. 아무리 우리가 할 수있는 것 하루의 끝에 컴퓨터, 하드웨어는 여전히 인 후드 아래 같은. 어떻게 여기에 단어를 저장할 것인가? 음, 컴퓨터에서 단어처럼 "이봐!" 다만 다음과 같이 저장됩니다. 그리고 당신은 더 이상을 원한다면 단어, 당신은 단순히 수 그 덮어 쓰기 뭔가 말 여기에 "안녕하세요"와 상점이있다. 

그리고 여기, 너무,이 인접에 이점은, 실제로 컴퓨터가 단지 수 있으므로 오른쪽에서 왼쪽으로 읽습니다. 그러나 여기 질문입니다. 이 단어의 맥락에서, H-전자 1-1 - 오, 느낌표, 컴퓨터가 위치를 알 수있는 방법 단어가 시작되고 말씀이 끝나는? 숫자의 맥락에서, 방법을 컴퓨터가 수행 노하우 순서의 길이 숫자 또는이 시작하는 위치를? 글쎄, 그것은해서 돌출집니다 우리는 너무 많이 가지 않을 것이다 detail--이 수준에 컴퓨터 메모리에 주위에 물건을 이동 말 그대로이 주소의 방법으로. 당신이 있다면, 컴퓨터에 따라서 코드를 작성하는 일을 저장하기 말처럼, 당신은 무엇이야 정말 입력됩니다 일 에 기억 식 컴퓨터의 메모리 이러한 단어입니다. 그래서 나를 매우을하자, 아주 간단한 예. 

내가 가서거야 및 간단한 텍스트 프로그램을 열고, 내가 만들거야 파일은에서는 hello.c했다. 이 정보의 대부분은 우리 훌륭한 세부 사항에로 가지 않을 것이다, 그러나 나는 쓰기거야 같은 언어 프로그램, C. 이는 훨씬 더 협박 나는, 스크래치보다 주장 하지만 정신에 매우 유사합니다. 사실,이 곱슬 braces-- 당신이 할 수있는 종류의 난 그냥이 같은 짓을 생각합니다. 

의 실제로,이 작업을 수행 할 수 있습니다. 녹색 깃발을 클릭하면, 다음을 수행하십시오. 나는 인쇄 할 "안녕하세요." 그래서 지금은 의사입니다. 나는 종류의 라인을 흐리게하고있다. C에서,이 언어 내가 말하는거야 약이 줄 인쇄 인사 실제로 "의 printf"으로된다 일부 괄호와 세미콜론. 

그러나 똑같은 생각이다. 그리고 이것은 매우 사용하기 쉬운 "녹색 깃발을 클릭하면"된다 훨씬 더 난해한 "INT 주요 무효." 그리고 이것은 정말 매핑이 없습니다, 그래서 나는 그냥 무시하는거야. 그러나 중괄호는 같다 이 같은 곡선 퍼즐 조각. 

그래서 당신이 할 수있는 종류의 같아요. 심지어, 이전에 프로그램 된 적이없는 경우 이 프로그램은 아마도 무엇을합니까? 아마 안녕하세요 인쇄 느낌표. 

그럼 그 시도 할 수 있습니다. 나는 그것을 저장하는거야. 그리고 이것은 다시, 아주이다 오래된 학교 환경을 제공합니다. 내가 드래그 할 수 클릭 할 수 없습니다. 나는 명령을 입력해야합니다. 그래서 정말, 내 프로그램을 실행하려면 나는에서는 hello.c처럼,이 작업을 수행 할 수 있습니다. 그건 내가 실행 파일입니다. 하지만이 단계를 실종 해요 기다립니다. 무엇 않았다 우리가 말할 것은 필요하다 C와 같은 언어 단계? 난 그냥 소스를 작성했습니다 코드, 그러나 나는 무엇을해야합니까? 네, 컴파일러가 필요합니다. 여기 내 Mac에서 그래서, 내가 가지고 GCC 호출 된 프로그램, GNU C 컴파일러, 어느 날이 항아리 회전을 수행 할 수 있습니다 내 소스 코드에, 우리는 그것을 전화 할게, 기계 코드. 

그리고 나는 그것을 볼 수 있습니다, 또, 다음과 같이, 이러한 0과 나는 단지 내 소스 코드에서 생성, 0과 1의 모든. 그리고 실행하려면 내 program--이 발생 대한 a.out의 호출되는 역사적 reasons-- "안녕하세요." 나는 다시 실행할 수 있습니다. 안녕 안녕 안녕. 그리고 그것은 작동하는 것 같군. 

그러나 그것은 어딘가에 의미 내 컴퓨터의 메모리 단어입니다 H-전자 1-1 - 오, 느낌표. 그리고, 옆 단지로 판명 어떤 컴퓨터는 일반적으로 것 그래서 위치를 알고 그렇게 일 시작하고 그것의 end-- 여기에 특수 기호를 넣을 것. 그리고 규칙은 넣어하는 것입니다 단어의 끝 수가 제로 당신은 어디를 알 수 있도록 실제로, 종료 있도록 더 자세한 내용을 인쇄 보관하지 마십시오 당신보다 문자가 실제로 계획입니다. 

그러나 여기 테이크 아웃도 이 상당히 비밀입니다 만, 그것은 궁극적으로는 것이다 비교적 간단합니다. 당신은 빈 테이프의 종류를 부여했다 당신이 편지를 쓸 수있는 공간입니다. 당신은 단순히 있어야 임의 같은 특수 기호, 수 제로의 단부에 넣어 단어 즉 컴퓨터가 인식 할 수 있도록, 오, 나는 후 인쇄를 중지해야합니다 나는 느낌표를 참조하십시오. 이 다음 일 때문에 제로의 ASCII 값이며, 또는 null 문자로 누군가를 부를 것이다. 그러나 문제의 종류있다 여기에, 그리고 이제 되돌릴 수 있습니다 잠시 숫자. 내가 가정 해 있다는 사실, 숫자의 배열을 가지고 하고 있음을 가정 내가 쓰고 있어요 프로그램입니다 교사에 대한 등급 책 등 그리고 교사 교실. 그리고이 프로그램은 그 사람이나 그 여자를 수 학생들의 점수를 입력합니다 퀴즈에. 그리고 학생이 도착한다고 가정 첫 퀴즈 100, 어쩌면 다음 다음 하나에 80, 등 (75) 다음, 제 90 퀴즈. 

이야기를이 시점에서 그래서, 어레이 크기가 네이다. 절대적으로 더 많은 메모리가에있다 컴퓨터가 있지만, 배열 때문에, 말하자면 네 크기이다. 교사가 원하는 것을 지금 가정 클래스에 다섯 번째 퀴즈를 할당합니다. 음, 것들 중 하나 그는 또는 그녀는해야 할 것입니다 지금 여기에 추가로 값을 저장합니다. 하지만 배열의 경우 교사는이 이 프로그램에서 만든이, 대한 크기입니다 어레이의 문제점 중 하나는이고 당신은 메모리에 계속 추가 할 수 없습니다. 때문에 어떤 경우의 다른 부분 프로그램은 바로 "안녕하세요"라는 단어가? 

즉, 내 메모리가 될 수있다 프로그램에서 아무것도에 사용됩니다. 그리고 사전에 나는, 헤이에 입력 한 경우 I 입력 사 퀴즈 점수하려는, 그들은 여기와 여기에 갈 수 있습니다. 그리고 당신은 갑자기 당신의 마음을 변경하는 경우 이상과 내가 다섯 번째 퀴즈 싶은 말 점수, 당신은 할 수 없습니다 만 당신이 원하는 목적지 넣어, 때문에 어떤이있는 경우 메모리가 사용되고 뭔가 다른 프로그램을 else-- 또는 프로그램의 다른 기능 당신은 실행하고 있는지? 그래서 당신은 사전에 생각해야 당신이 당신의 데이터를 저장하는 방법, 지금 당신이 그린 것 때문에 자신 디지털 코너에. 

그래서 선생님이 대신 수도 프로그램을 작성할 때 말 저장하기 위해 자신의 등급, 그거 알아? 나는 요청할 예정 내 프로그램을 작성할 때, I이 원하는 제로, 하나, 둘, 셋, 넷, 다섯, 여섯, 여덟 등급 총. 따라서 하나, 둘, 셋, 넷, 다섯, 여섯, 일곱, 여덟. 선생님은 그냥-할당 할 수 있습니다 메모리는 자신의 프로그램을 작성할 때 당신이 무엇을 알고, 말? 나는 결코 더 할당 않을거야 한 학기에 팔 퀴즈보다. 그건 그냥 미친 짓이야. 나는 그것을 할당하지 않을 것이다. 이 방법은 자신이을 갖도록 매장 학생 점수 유연성, 75, 90, 어쩌면 하나의 추가 등 학생은 105 여분의 신용을 얻었다. 

그러나 만약 교사 결코 이 세 공간을 사용, 여기에 직관적 인 테이크 아웃이있다. 그 또는 그녀는 단지 공간을 낭비한다. 환언하면,이 거기 프로그래밍에서 흔히 트레이드 오프 당신도 할당 할 수있는 정확하게 많은 메모리 당신이 원하는대로, 의 상승은 슈퍼 걸이다 efficient-- 당신은 낭비되지 않는 것 에서 all-- 만의 단점 무엇 당신은 당신의 마음 때를 변경하는 경우 저장하려는 프로그램을 사용하여 당신보다 더 많은 데이터가 원래 의도. 

그래서 어쩌면 용액 후이며 이와 같은 방법으로 프로그램을 작성 그들은 더 많은 메모리를 사용하는 것이 그들은 실제로 필요한 것보다. 당신은하지 않을거야 이런 식으로 그 문제로 실행하려면, 하지만 당신은 낭비되고 있습니다. 그리고 프로그램이 사용하는 메모리, 우리는 어제 한 바와 같이, 이하 가능한 메모리 다른 프로그램, 빨리 컴퓨터가 느려질 수 있습니다 아래로 인해 가상 메모리. 그래서 이상적인 솔루션은 무엇을 할 수 있는가? 

에서 할당하는 나쁜 것 같다. 오버 할당하는 나쁜 것 같다. 그래서 더 나은 해결책이 될 수 있는가? 재 할당. 보다 역동적합니다. 을 선택하는 자신을 강요하지 마십시오 사전은, 처음에, 당신은 무엇을 할 수 있습니다. 그리고 확실히, 과다 할당하지 않습니다 당신 않도록 낭비. 

그리고 그 목표를 달성하기 위해, 우리 이 데이터 구조를 던질 필요가있다, 그래서 멀리, 말을합니다. 그래서 어떤 프로그래머 일반적으로 사용합니다 아닌 뭔가라고 배열하지만,​​ 연결리스트. 환언하면, 그 또는 그녀는 것 자신의 메모리를 생각하기 시작 모양의있는 일종의 그들이 다음과 같은 방법으로 그릴 수 있습니다. 나는 하나의 번호를 저장하려면 그것은 9 월 있도록 program--, 나는 학생들에게 퀴즈를 준; 내가 원하는 학생들의 첫 번째 퀴즈를 저장, 그들은 그건 ... I에 100있어 내 컴퓨터를 요청할 예정이다, 나는했습니다 프로그램의 방법으로 메모리의 청크에 대한 서면. 그리고 나는를 저장하는거야 거기에 번호 100, 그게입니다. 

그리고 몇 주 후 내 두 번째 퀴즈를 얻을 때, 그리고 입력하는 시간 그 90 %에, 내가 갈거야 컴퓨터를 물어, 헤이, 컴퓨터, 나는 메모리의 다른 청크를 가질 수있다? 나에게이 줄거야 메모리의 빈 덩어리. 나는 숫자 90에 넣어거야 하지만 내 프로그램에 어떻게 든 또는 다른 것이라면 우리는 걱정하지 않습니다 내가 필요로하는이 항아리에 대한 구문 어떻게 든에 함께이 일을 체인. 그리고 함께 그들을 체인 것 무슨 일이 여기에 화살처럼 보인다. 

온다 세 번째 퀴즈, 내가 말할거야, 이봐, 컴퓨터, 나에게 메모리의 다른 청크를 제공합니다. 내가 내려 갈거야 어떤 것은 75와 마찬가지로했다 나는 체인이에있다 함께 지금 어떻게 든. 네 번째 퀴즈는 따라오고, 어쩌면 그 학기의 끝을 향해입니다. 그리고 그 때 내 프로그램에 의해 메모리를 사용 될 수 있습니다 도처에, 모든 물리적으로 이상. 그래서 그냥 재미로 들어 난 이 규정 그릴 예정 quiz-- 나는 그것이 무엇인지 잊어; 나는 어쩌면 생각 80 또는 뭔가 ... 방법을 통해 여기에. 

하지만 그 때문에 그림으로, 괜찮아요 나는이 선을 그릴거야. 즉, 실제로 컴퓨터의 하드웨어, 첫 번째 점수 수도 그것 때문에 여기까지 바로 학기의 시작. 다음 하나는 여기에 끝낼 수 있습니다 약간의 시간이 경과했기 때문에 프로그램 실행 유지합니다. 이었다 다음 점수, 75는 여기에있을 수 있습니다. 그리고 마지막 점수 수 있습니다 여기있는 80. 

그래서 현실에서, 물리적,이있을 수 있습니다 어떤 컴퓨터의 메모리는 것 같습니다. 그러나 유용한 정신 아니다 컴퓨터 프로그래머를위한 패러다임. 왜 당신이 어디에 관심을 가져야 도대체 데이터가 끝나는입니까? 당신은 데이터를 저장할. 

이것은 우리의 토론과 같은 종류의 것입니다 큐브를 그리기 이전. 왜 상관이야 무엇 각도 큐브 인 어떻게 당신은 그것을 그릴 설정해야? 당신은 큐브를 할 수 있습니다. 마찬가지로 여기, 당신을 단지 학년 책합니다. 당신은 생각 할 번호의 목록 등이. 그것의 방법을 누가 관심 하드웨어로 구현? 

이제 추상화 그래서 여기이 사진입니다. 이 같이 목록에서 연결된한다 프로그래머는 부를 것이다, 당신은이하는 한 목록, 분명 번호. 그러나 그림으로 연결되어있어 이 화살표의 방법으로, 이 모든 화살표가 아래으로 죠 후드, 당신은 호기심이 있다면, 우리의 물리적 하드웨어가 가지고있는 기억 주소는 하나, 둘, 셋, 넷 제로. 이러한 모든 화살표는지도처럼 또는 방향의 경우 90 is-- 지금 나는 계산되었다. 

제로, 하나, 둘, 셋, 넷, 다섯, 여섯, 일곱. 90가에있을 것 같습니다 메모리 주소 번호 일곱. 이러한 모든 화살표는있다 종이의 작은 스크랩 등 그것은에 방향을주고 이지도를 따라 말한다 프로그램 위치 일곱에 도착합니다. 그리고 거기 당신은 찾을 수 학생의 두 번째 퀴즈 점수. 한편, 75-- 나는 이것을 계속하면, 이 일곱, 여덟, 아홉, 열, 11, 12, 13, 14, 15. 

이 다른 화살표는 나타냅니다 메모리 위치 (15)에 대한지도. 그러나 다시, 프로그래머는 일반적으로 수행 세부 사항이 수준에 대해 걱정하지. 그리고 대부분의 모든 프로그래밍 언어 오늘, 프로그래머 경우에도 메모리에 알 수 없습니다 이 숫자는 사실이다. 그 또는 그녀가이 모든 약 한 관심 그들은 어떻게 든 서로 연결되어 있음 이와 같은 데이터 구조이다. 

그러나 그렇지 밝혀 너무 기술적 얻을 수 있습니다. 그냥 있기 때문에 우리는 아마도 수 여기 토론을 할 여유, 우리가 방문한다고 가정 여기에 배열의이 문제. 우리가 여기가는 후회하는 경우 보자. 이것은 100, 90, 75, 80이다. 

내가 간단히 이러한 주장을 만들어 보자. 이 배열하고, 다시, 배열의 두드러진 특징 모든 데이터는 다시 있다는 다시 말 그대로 me​​mory--에 백업 할 한 바이트 또는 어쩌면 4 바이트, 멀리 바이트의 몇 가지 고정 된 수의. 링크 된 목록에서, 우리는 그릴 수있는 이 같은 후드 아래에있는 사람 그 물건이 어디 있는지 아는 사람? 심지어이 같은 흐름 필요가 없습니다. 데이터의 일부가 될 수있다 다시는 거기에서 왼쪽으로. 당신은 몰라. 

그래서 배열과 함께, 당신은이 랜덤 액세스로 알려진 기능입니다. 그리고 무엇 랜덤 액세스 수단 것은 컴퓨터가 즉시 이동할 수 있음 배열의 모든 위치. 왜? 컴퓨터가 알고 있기 때문에 첫 번째 위치는 그 영, 하나, 둘, 3. 

그래서 당신이에서 가고 싶은 경우 다음 요소로이 요소, 당신 그대로의 컴퓨터의 마음은 하나를 추가합니다. 세 번째 요소로 이동하려면, 그냥, 다음 요소 one-- 추가 하나를 추가 할 수 있습니다. 그러나이 버전의 이야기의, 가정 컴퓨터가 현재 찾고 이나 수 (100)를 처리. 어떻게 당신이 다음에 어떻게해야합니까 학년 책에 등급? 

당신은 칠을해야 임의 단계. 다음 단계로 얻으려면, 당신은에 있습니다 (15)에 도착하는 또 다른 팔 조치를 취합니다. 즉,이 아니다 숫자 사이에 일정한 갭 그래서 그냥 소요 컴퓨터에 더 많은 시간이 포인트입니다. 컴퓨터가 검색 할 수있다 위해 메모리를 통해 당신이 찾고있는 것을 찾을 수 있습니다. 

배열이 될 경향이있는 반면 그래서 빠른 데이터 structure-- 당신 때문에 말 그대로 단순한 연산을 수행 할 수 있습니다 하나를 추가하여 원하는 위치를 얻을, 링크 된 목록을 instance--를 들어, 해당 기능을 희생. 당신은 처음부터 갈 수 없어 두 번째 세 번째에에 네 번째이다. 당신은지도를 수행해야합니다. 당신은 더 많은 조치를 취할 필요가 그 값을 얻을 수있는 비용을 추가로 보인다. 그래서 우리는 가격을 지불하지만, 무엇 이었습니까하고 단 여기서 추구하는 것을 특징? 무엇 링크 된 목록을 수행 분명히 우리가 할 수 있도록, 어떤의 기원이었다 이 특별한 이야기​​? 

정확하게. 그것을 동적 크기입니다. 우리는이 목록에 추가 할 수 있습니다. 우리는 심지어 그래서 목록을 축소 할 수 있습니다 우리는 많은 메모리를 사용하고 있는지 우리가 실제로 원하는 등 우리는 과도하게 할당하는 적이있어 없습니다. 

지금 바로, 정말 NIT-까다 롭고 될 수 있습니다 숨겨진 비용이있다. 그래서 당신은 나를 설득 못하게한다 당신이 강제적 절충된다. 여기에 또 다른 숨겨진 비용이있다. 이점은 명확합니다 우리가 활력을 얻을 것입니다. 나는 다른 요소를 원하는 경우에, 난 그냥 수 그것은을 그리고 거기에 숫자를 넣어. 그리고 나는 그것을 연결할 수 있습니다 여기에 사진과 함께, 여기 반면, 다시, 나는했습니다 경우 , 구석으로 자신을 그린 뭔가가 이미 사용하고있는 경우 여기에 메모리, I는 운입니다. 나는 구석으로 자신을 그린했습니다. 

그러나 숨겨진을 무엇 이 그림에서 비용? 그것은 단지 양이 아니다 걸리는 시간 여기에 여기에서 이동합니다, 이는 다음, 일곱 단계입니다 이상입니다 여덟 단계. 또 다른 숨겨진 비용은 무엇입니까? 다만 시간. 추가 정보는 필요한이 사진을 달성했다. 

그래,지도,의 그 작은 조각 종이, 내가 그들을 설명하는 유지로. 그 arrows--이 무료하지 않습니다. 당신이 알고있는 computer-- 컴퓨터는 무슨. 그것은 0과 1을 보유하고 있습니다. 당신은 화살표 또는를 표현하려면 지도 또는 숫자, 당신은 일부 메모리가 필요합니다. 다른 가격 그래서 링크 된 목록을 지불, 일반적인 컴퓨터 과학 자원은 또한 공간이다. 

그리고 실제로 그렇게 때문에 일반적으로, 장단점 중 소프트웨어 공학 설계에 시스템 시간이다 space-- 당신의 재료의 두 ​​개의 가장 비용이 많이 드는 재료. 이것은 나에게 더 많은 시간을 원가 계산된다 나는이지도를 수행해야하기 때문에, 그러나 그것은 또한 나에게 더 많은 공간을 비용 것 나는이지도를 계속해야하기 때문이다. 그래서 희망으로 우리는 가지했습니다 어제와 오늘에 걸쳐 논의, 이점이다 비용을보다 중요한 것입니다. 

그러나 여기에는 확실한 해결책은 없습니다. 아마 better--입니다 라 신속하고 더러운, 카림은 earlier-- 제안으로 문제의 메모리를 던져. 그냥 더 많은 메모리를 구입, 덜 생각 문제 해결에 대한 하드, 하고 쉬운 방법으로 그것을 해결. 그리고 실제로 이전 할 때 우리는 장단점에 대해 이야기, 그것은 공간이 아니었다 컴퓨터 및 시간입니다. 그것은 개발자의 시간이었다 또 다른 자원이다. 

그래서 다시,이 조정 행위이다 결정하려고 그런 일이있는 당신이 지출 할 수 있습니까? 가장 저렴한는 무엇입니까? 어느 것이 더 나은 결과를 얻을? 네? 

과연. 이 경우라면 maps--의 숫자를 나타내는 이러한 많은 언어라고합니다 "포인터"또는 "주소"- 이 두 공간입니다. 그 경우 이중으로 나쁜 일 필요는 없다 지금 우리는 단지 숫자를 저장하고 있습니다. 우리가 저장되었다고 가정하자 hospital--에서 환자 기록 피어슨의 이름, 전화 번호 때문에, 사회 보장 번호, 의사 역사. 이 상자는, 많은 수 있습니다 훨씬 더 큰 경우에 작은 작은 포인터의 주소 다음은 큰 문제가 아니다 element--. 그러한 프린지의 그것은 중요하지 않습니다 비용. 그러나이 경우, 그래, 그것은 두 배입니다. 좋은 질문. 

의 시간 a를 이야기하자 보다 구체적으로 조금. 실행 시간 무엇입니까 이 목록을 검색하는? 내가 검색을 원 가정 모든 학생들의 성적을 통해, n은 성적을 거기에 데이터 구조이다. 여기에서도 우리는 빌릴 수 이전의 어휘. 이것은 선형 데이터 구조이다. 

(n)의 빅 O를 얻을 필요가있는 무슨이다 데이터 구조의 끝, whereas-- 우리는 보지 못했어요 이 배열을 제공 before-- 무엇을 의미하는 일정 시간이라고 한 단계 또는 두 단계 또는 10 steps-- 중요하지 않습니다. 그것은 고정 된 수 있습니다. 그것은 함께 할 수 없다 배열 크기. 그리고 그 이유, 또, 랜덤 액세스이다. 컴퓨터 수 단지 바로 다른 위치로 이동, 그들은 모두 같은이기 때문에 다른 모든 것들로부터 거리. 반군 생각은 없습니다. 괜찮아. 내가 할 수있는 경우에 그래서, 내가하려고하자 이 마지막 사진을 페인트. 해시 테이블로 알려진 매우 일반적인 일. 그래서이 토론 동기를 부여하고, 내가이 작업을 수행하는 방법에 대해 생각해 보자. 

그래서 방법에 대해? 문제가 있다고 가정 우리는 지금 해결하려는 dictionary--에서 구현된다 영어 단어 때문에 전체 무리 또는 무엇 이건. 그리고 목표는 대답 할 수있을 것입니다 형태의 질문이있는 단어입니다? 그래서 당신이 구현하려는 맞춤법 검사기, 단지 물리적 사전 등 당신이 물건을 검색 할 수. 내가 배열이 작업을 수행하는 가정하자. 나는이 작업을 수행 할 수 있습니다. 

그리고 단어가 사과입니다 가정 바나나와 멜론. 그리고 나는 과일 생각할 수 없다 즉, D로 시작하는, 그래서 우리는 그냥있어 세 가지 과일을해야 할 것. 그래서이 배열이며, 우리는있어 이 모든 단어를 저장 배열 등이 사전입니다. 문제는, 그 후, 다른 방법 인 이 정보를 저장할 수 있을까? 

글쎄, 난 가지 있기 때문에, 여기에 바람을 피우고있어 단어 이러한 문자의 각 정말 개인 바이트입니다. 그래서 내가 정말되고 싶어하는 경우 알 - 까다 롭고, 정말해야 많은이 점을 나누어 할 수 메모리의 작은 덩어​​리, 우리는 정확하게 할 수 있습니다. 그러나 우리는로 실행거야 이전과 같은 문제. 뭐, 만약 메리 엄 웹스터 또는 옥스포드 등 모든 그들이 단어를 추가 연도 - 않습니다 dictionary--에 우리는하지 않습니다 반드시 자신을 페인트 할 배열 함께 한 구석에? 

그래서 그 대신, 어쩌면 현명한 방법 자신의 노드 또는 상자에 사과를 넣어하는 것입니다, 우리가 말할 것 같은, 바나나,과 여기에 우리는 멜론이 있습니다. 이러한 것들을 함께 그리고 우리 문자열입니다. 그래서 배열이고, 이 링크 된 목록입니다. 당신은 매우 볼 수없는 경우, 단지 말한다 "배열"이 말한다 "목록을." 

그래서 우리는 같은이 이전과 정확한 문제, 이에 우리가 지금해야 우리의 연결리스트의 역 동성. 그러나 우리는 상당히 느린 사전을 가지고있다. 나는 단어를 검색한다고 가정. 그것은 나에게 (n)의 큰 O 걸릴 수 있습니다 단계, 단어 수 있기 때문에 끝에서 끝까지 될 멜론 같은 목록. 그리고 그것은 밝혀 프로그래밍 정렬 데이터의 성배의 구조, 뭔가 그건 당신이 상수 제공 배열과 같은 시간 하지만 여전히 당신에게 활력을 제공합니다. 

그래서 우리는 두 세계의 최고를 가질 수있다? 그리고 실제로 뭔가가있다 해시 테이블이라고 그건 당신이 정확하게 수행 할 수 있습니다 이기는하지만 약, 그. 해시 테이블은 애호가입니다 데이터 구조가 우리 로 생각할 수 있습니다 array--의 조합 나는 그것을 그릴거야 이 항아리와 연결리스트 등 나는 여기에 다음과 같이 그릴거야. 

이 일 그리고 방법 다음과 같은 작품이다. 이 table-- 해시 now-- 경우 제 3 데이터 구조이며, 나는 저장할 이 단어, 난 몰라 그냥 모두를 저장할 말은 다시 다시 다시 다시합니다. 나는 몇 가지를 활용하려면 정보의 조각 드릴 것입니다 단어에 대한 더 빨리 어디 내가 그것을 얻을. 

그래서 단어 사과를 부여 바나나, 멜론, 나는 일부러 그 단어를 선택했다. 왜? 무엇의 근본적 일종의 세 가지에 대해 다른? 명백한은 무엇입니까? 그들은 서로 다른 문자로 시작합니다. 

그래서 당신은 무엇인지? 모든 내 말을 넣어보다는 같은 버킷은, 그래서, 말하자면 같은 하나의 큰 목록에서 왜하지 나는 적어도 최적화를 시도 내 목록을 1/26로 긴합니다. 눈길을 끄는 최적화 하지 않는 이유가 될 수 있습니다 난 ... 때 단어를 삽입 데이터 구조로, 컴퓨터의 메모리, 왜에 나는 여기에 모든 '은'단어를 넣어하지 않습니다 모든 여기에 'B'즉, 여기에 모든 'C'단어? 그래서이 사과를 넣어 끝 여기, 여기 여기 바나나, 멜론, 기타 등등. 

그리고 추가로있는 경우 말은 다른 무엇 이렇게 ...? 사과, 바나나, 배. 사람은 과일의 생각 즉 A, B 또는 C로 시작? Blueberry-- 완벽한. 즉, 여기에 끝날 것입니다. 그래서 우리는 것 같다 소폭 더 나은 솔루션, 지금 내가 원하는 경우 때문에 사과를 검색하려면, I first-- 난 그냥 다이빙을하지 않습니다 내 데이터 구조로. 내 컴퓨터의 메모리에 뛰어하지 않습니다. 내가 먼저 첫 글자를 봐주세요. 

그리고 이것은 어떤 컴퓨터입니다 과학자는 말할 것입니다. 당신은 당신의 데이터 구조로 해시. 당신은 당신의 입력에 걸릴 이 경우는 사과와 같은 단어입니다. 당신은보고, 그것을 분석 이 경우 첫 글자, 따라서 그것을 해시. 해싱은 일반적인 용어된다이다 당신은 입력으로 뭔가를 취할 당신은 몇 가지 출력을 생성합니다. 그리고에서 출력 경우는 위치입니다 만약 제를 검색 할 위치, 두 번째 위치, 세 번째. 그래서 입력 사과입니다, 출력은 처음이다. 입력은 바나나의입니다 출력은 두 번째 있어야합니다. 입력은, 멜론입니다 출력은 세 번째해야한다. 입력은 베리이며 출력은 다시 두 번째 있어야합니다. 그리고 당신이 걸릴 수 있습니다 무엇 당신의 기억을 통해 바로 가기 단어에 도착하기 위해 또는 데이터를보다 효율적으로. 

지금 이것은 잠재적으로 우리의 시간을 줄인다 많은 26 중 하나에 의해, 당신이 가정한다면 당신 때문에 그 "Z"많은 "에"단어가 "Q"단어와 같은 단어한다 정말 realistic--되지 않습니다 당신은에 걸쳐 왜곡을 할거야 alphabet--의 특정 문자 하지만이 증가 될 것 수 않는 방법 당신은 훨씬 빠르게 단어를 얻을 수 있습니다. 그리고 현실에서, 정교한 프로그램, 세계의 구글, 을 전 세계의 Facebooks 이들은 해시 테이블을 사용 다른 목적을 많이합니다. 그러나 그들은 같은 순진되지 않을 것 단지 첫 글자를보고 사과 또는 바나나 또는 배 또는 멜론, 당신이 볼 수 있기 때문에 목록은 여전히​​ 긴 얻을 수 있습니다. 

그리고이 여전히 종류의 수 있습니다 의 linear-- 그래서 일종의 느린, N의 큰 O와 같은 것을 우리는 앞에서 언급. 그래서 정말 좋은 해시 테이블 것 그것은 훨씬 더 큰 배열을해야합니다 do--. 그리고 그것은 훨씬 더를 사용합니다 정교한 해시 함수 있도록 그냥 보지 않는다 "는." 어쩌면 그것은 보인다 "는-P-P-1-전자"와 어떻게 든 그 다섯 글자로 변환 어디 위치에 사과 저장해야합니다. 우리는 순진 문자 'A'를 사용하는 혼자, 그것은 좋은 간단하기 때문이다. 

그러나 해시 테이블에 결국, 당신은 생각할 수 의 조합으로서 어레이, 각각의 그 이상적으로 링크 된 목록을 가지고 가능한 한 짧아야한다. 그리고 이것은 명백한 해결책이 아니다. 미세 조정의 사실, 많은 즉, 후드 때 아래에 간다 이러한 종류의 구현 복잡한 데이터 구조 오른쪽은 무엇인가 어레이의 길이? 오른쪽 해시 함수는 무엇인가? 어떻게 메모리에 물건을 저장합니까? 

하지만 얼마나 빨리 실현 토론 이러한 종류의 이 종류의 것을, 중 지금까지 에스컬레이션 이 시점에서 하나의 머리 위에있는 괜찮습니다. 그러나 우리는 진정으로, 리콜을 시작 뭔가 낮은 수준의 전자. 그리고 이것은 다시입니다 추상화의 테마, 어디 걸릴하기 시작하면 부여, OK, 나는 거기에 그건 ...에게있어 실제 메모리, OK, 모든, 그것을 가지고 물리적 위치는 주소를 가지고 OK, 그것을 가지고 내가, 내가 표현할 수있다 arrows--으로 해당 주소 당신은 매우 신속하게 가지고 시작할 수 있습니다 보다 정교한 대화가 결국 우리를 허용 할 것 검색 같은 문제점을 해결하기 위하여 보다 효과적으로 정렬. 그리고, 너무 ... 안심 나는 이것을 생각하기 때문에 우리는 몇 가지로 갔어요 깊은이다 우리가했습니다 proper--이 CS 주제 이에서 하루 반에서 수행 당신은 일반적으로 이상 할 수있는 것을 가리 킵니다 한 학기에 8 주 과정. 

이들에 대한 질문? 아니? 괜찮아. 그럼, 왜 우리가 일시 중지하지 않습니다, 몇 분 일찍 점심을 시작, 단지 한 시간 정도에 재개? 그리고 난에 대한 남아 있습니다 질문 좀. 그럼 내가 가야 할거야 그 확인의 경우 몇 전화를 가져 가라. 나는 그 동안 어떤 음악을 설정합니다 하지만 점심 모퉁이해야합니다.