1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [음악 연주] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID 마란 :이 CS50입니다. 5 00:00:14,010 --> 00:00:18,090 그리고 이것은 시작과 둘 다 literally-- 거의 말처럼 end-- 6 00:00:18,090 --> 00:00:18,825 주 여섯. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> 나는를 공유하고자합니다 재미있는 사실 조금. 9 00:00:22,640 --> 00:00:25,370 나는에서이 뽑아 봤어 지난 학기의 데이터를 설정합니다. 10 00:00:25,370 --> 00:00:29,710 당신은 우리가 매일에 요청할 것을 기억하고있을 것 P 세트 형태로 온라인 시청 한 경우 11 00:00:29,710 --> 00:00:31,580 또는 당신은 사람에 참석 한 경우. 12 00:00:31,580 --> 00:00:33,020 그리고 여기에 데이터입니다. 13 00:00:33,020 --> 00:00:34,710 그래서 오늘은 매우 예측했다. 14 00:00:34,710 --> 00:00:37,126 그러나 우리는 조금을 보내고 싶어 시간을 당신과 함께 그럼에도 불구하고. 15 00:00:37,126 --> 00:00:40,599 사람이 왜이 추측 하시겠습니까 그래프, 위로 아래로, 위로 아래로, 그래서 톱니입니다 16 00:00:40,599 --> 00:00:41,265 그래서 지속적으로? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 어떤 피크의 각을 과 최저점 대표? 19 00:00:45,130 --> 00:00:46,005 >> 청중 : [들리지] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID 마란 : 사실. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 그리고 더 재미있게, 신 금지, 우리는 금요일에 한 강의를 개최 24 00:00:55,480 --> 00:00:58,960 학기의 시작 부분에서, 그것은 우리가 일을 참조거야. 25 00:00:58,960 --> 00:01:03,430 그래서 오늘, 우리는 조금에 참여 데이터 구조에 대한 자세한. 26 00:01:03,430 --> 00:01:06,660 그리고 당신에게 고체의 더주고 다섯에서 문제에 대한 정신 모델, 27 00:01:06,660 --> 00:01:07,450 이는 지금 밖으로이다. 28 00:01:07,450 --> 00:01:10,817 맞춤법 오류 항에있어서, 우리는거야 당신에게 텍스트 파일을 손으로 10 만명 29 00:01:10,817 --> 00:01:12,650 플러스 영어 단어 및 당신은 할거야 30 00:01:12,650 --> 00:01:17,770 영리를로드하는 방법을 알아 내기 위해 메모리, RAM에, 일부 데이터를 사용하여 31 00:01:17,770 --> 00:01:19,330 당신의 선택의 구조. 32 00:01:19,330 --> 00:01:22,470 >> 이제 하나의 데이터 구조는 수 안 아마 수 있지만, 33 00:01:22,470 --> 00:01:25,630 상당히 단순 연결리스트, 이는 우리가 지난 시간에 소개했다. 34 00:01:25,630 --> 00:01:29,220 그리고 연결리스트는 적어도했다 배열을 통해 하나의 장점. 35 00:01:29,220 --> 00:01:32,096 하나의 이점은 무엇입니까 틀림없이 연결리스트? 36 00:01:32,096 --> 00:01:32,950 >> 청중 : 삽입. 37 00:01:32,950 --> 00:01:33,908 >> DAVID 마란 : 삽입. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 당신은 무엇을 의미합니까? 40 00:01:35,196 --> 00:01:37,872 >> 청중 : 어디에나 목록 [들림]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID 마란 : 좋은. 42 00:01:38,770 --> 00:01:42,090 그래서 당신은 요소마다 삽입 할 수 있습니다 사용자는 목록의 중간에 원하는 43 00:01:42,090 --> 00:01:45,490 아무것도 셔플하지 않고, 이는 우리가 우리의 정렬에 결론 44 00:01:45,490 --> 00:01:47,630 토론이 아니다 반드시 좋은 일이, 45 00:01:47,630 --> 00:01:51,200 그것은 시간이 걸리기 때문에 실제로 이동 그 사람의 모든 왼쪽 또는 오른쪽으로. 46 00:01:51,200 --> 00:01:55,540 그리고 연결리스트, 당신은 할 수 단지의 malloc으로 할당, 새 노드, 47 00:01:55,540 --> 00:01:58,385 다음의 몇 가지를 업데이트 pointers-- 두, 세 가지 작업이 max-- 48 00:01:58,385 --> 00:02:01,480 우리는 사람을 슬롯 수있어 목록에 어디에서. 49 00:02:01,480 --> 00:02:03,550 >> 또 어떤 유익했다 링크 된 목록에 대한? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 그래? 52 00:02:05,659 --> 00:02:06,534 >> 청중 : [들리지] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID 마란 : 완벽한. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 완벽한. 57 00:02:11,090 --> 00:02:12,070 정말 동적입니다. 58 00:02:12,070 --> 00:02:15,100 그리고 당신은 투입하지 않을 것을, 사전에 어떤 고정 된 크기 59 00:02:15,100 --> 00:02:18,750 메모리의 덩어리처럼 당신은 것 배열, 위쪽에있는의 60 00:02:18,750 --> 00:02:22,455 만에 노드를 할당 할 수있다 요구함으로써 만 많은 공간을 사용하여 61 00:02:22,455 --> 00:02:23,330 당신이 실제로 필요로하는. 62 00:02:23,330 --> 00:02:26,830 배열과는 달리, 당신은 수도 실수로 너무 적게 할당합니다. 63 00:02:26,830 --> 00:02:28,871 그리고 그것은 단지거야 목에 통증이있을 수 있습니다 64 00:02:28,871 --> 00:02:32,440 새로운 더 큰 배열을 재 할당, 복사 모든 통해, 기존의 배열을 해제 65 00:02:32,440 --> 00:02:33,990 다음의 비즈니스에 대해 이동합니다. 66 00:02:33,990 --> 00:02:37,479 더 나쁜, 당신은 길을 할당 할 수 있습니다 당신이 실제로 필요한 것보다 더 많은 메모리, 67 00:02:37,479 --> 00:02:40,520 그래서 당신은 매우를 할 겁니다 말하자면, 배열을 드문 드문 채워진. 68 00:02:40,520 --> 00:02:44,350 >> 그래서 링크 된 목록이 당신에게 제공 활력과 유연성의 장점 69 00:02:44,350 --> 00:02:46,080 삽입과 삭제와. 70 00:02:46,080 --> 00:02:48,000 그러나 확실히 지불 가격이 있어야합니다. 71 00:02:48,000 --> 00:02:50,000 테마의 사실, 하나 퀴즈 제로 탐험 72 00:02:50,000 --> 00:02:52,430 했다 절충의 몇 우리는 지금까지 본 적이있다. 73 00:02:52,430 --> 00:02:56,161 그래서 유료 가격 또는 무엇 연결리스트의 하락? 74 00:02:56,161 --> 00:02:56,660 그래. 75 00:02:56,660 --> 00:02:57,560 >> 청중 : 없음 랜덤 액세스. 76 00:02:57,560 --> 00:02:58,809 >> DAVID 마란 : 아니 랜덤 액세스. 77 00:02:58,809 --> 00:02:59,540 하지만 누가 무슨 상관이야? 78 00:02:59,540 --> 00:03:01,546 랜덤 액세스는 강력한 소리를하지 않습니다. 79 00:03:01,546 --> 00:03:02,421 >> 청중 : [들리지] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID 마란 : 정확. 82 00:03:05,740 --> 00:03:07,580 당신이 갖고 싶어 특정 algorithm-- 83 00:03:07,580 --> 00:03:10,170 나 실제로 제안하자 특히 이진 검색, 어떤 84 00:03:10,170 --> 00:03:12,600 우리는 꽤 bit--를 사용했습니다 하나입니다 만약 랜덤 액세스가없는 경우에, 85 00:03:12,600 --> 00:03:15,516 당신은 간단한 산술 연산을 수행 할 수 없습니다 중간 요소처럼 발견 86 00:03:15,516 --> 00:03:16,530 그리고 바로 점프. 87 00:03:16,530 --> 00:03:20,239 대신 처음에 시작해야 요소와 선형 왼쪽에서 검색 88 00:03:20,239 --> 00:03:22,780 오른쪽에 당신은 발견 할 경우 중간 또는 임의의 다른 구성 요소 일 수있다. 89 00:03:22,780 --> 00:03:24,410 >> 청중 : 그것은 아마 더 많은 메모리가 소요됩니다. 90 00:03:24,410 --> 00:03:25,040 >> DAVID 마란은 : 더 많은 메모리를 이동합니다. 91 00:03:25,040 --> 00:03:27,464 어디 추가적인입니다 메모리에서 오는 비용? 92 00:03:27,464 --> 00:03:28,339 >> 청중 : [들리지] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID 마란 : 정확. 95 00:03:33,440 --> 00:03:35,679 여기서이 경우, 우리는이 있었다 정수에 대한 연결리스트, 96 00:03:35,679 --> 00:03:37,470 아직 우리는 배가있어 메모리의 양 97 00:03:37,470 --> 00:03:39,680 우리는 또한 이러한 포인터를 저장하여 필요합니다. 98 00:03:39,680 --> 00:03:42,090 같은 큰 문제가 지금 적은 당신의 구조체이 큰 얻을 99 00:03:42,090 --> 00:03:45,320 당신이하지 번호를 저장하고 있지만, 어쩌면 학생 또는 다른 객체입니다. 100 00:03:45,320 --> 00:03:46,880 그러나 중요한 점은 확실히 남아있다. 101 00:03:46,880 --> 00:03:49,421 그래서 다수의 동작 연결리스트에 전화를했다 102 00:03:49,421 --> 00:03:50,570 N-- 선형의 큰 O했다. 103 00:03:50,570 --> 00:03:54,730 삽입 또는 검색 같은 것들 또는 경우 요소의 삭제 104 00:03:54,730 --> 00:03:57,720 의 맨 마지막에 할 일 이 분류 여부를 여부 목록. 105 00:03:57,720 --> 00:04:01,167 >> 때때로 당신은 운과의 수 이러한 작업에 이렇게 하한 106 00:04:01,167 --> 00:04:04,250 당신이 있다면 또한 일정 시간이 될 수 있습니다 항상 첫 번째 요소에서 찾고, 107 00:04:04,250 --> 00:04:05,070 예를 들면. 108 00:04:05,070 --> 00:04:09,360 그러나 궁극적으로, 우리는 약속 성배를 달성하기 위해 109 00:04:09,360 --> 00:04:12,630 데이터 구조, 또는 일부 근사 그, 110 00:04:12,630 --> 00:04:14,290 일정 시간의 방법으로. 111 00:04:14,290 --> 00:04:17,579 우리는 요소를 찾거나 요소를 추가 할 수 있습니다 또는 목록에서 요소를 제거? 112 00:04:17,579 --> 00:04:19,059 우리는 아주 빨리 볼 것이다. 113 00:04:19,059 --> 00:04:21,100 그리고 그 하나를 밝혀 우리가하고있는 메커니즘 114 00:04:21,100 --> 00:04:23,464 오늘 사용하기 시작하는 것, P 연간 사용, 다섯 설정 115 00:04:23,464 --> 00:04:24,630 실제로 꽤 잘 알고있다. 116 00:04:24,630 --> 00:04:27,430 예를 들어,이 무리이면 시험 책, 각각의 117 00:04:27,430 --> 00:04:29,660 학생의 첫 번째가 거기에 이름과 성을 이름, 118 00:04:29,660 --> 00:04:31,820 나는 그들을에서 픽업 시험의 끝에, 119 00:04:31,820 --> 00:04:33,746 그리고 그들은 모든 꽤있어 임의의 순서로 많은, 120 00:04:33,746 --> 00:04:36,370 우리는 정렬에 대해 가고 싶어 이 시험은 그래서 한 번 등급 121 00:04:36,370 --> 00:04:38,661 그냥 더 쉽게 그리고 빨리 그들을 다시 손합니다 122 00:04:38,661 --> 00:04:40,030 알파벳 순으로 학생. 123 00:04:40,030 --> 00:04:42,770 당신의 본능은 무엇 일 것 이 같은 시험의 더미 하시나요? 124 00:04:42,770 --> 00:04:45,019 >> 글쎄, 당신이 저 같이 인 경우에, 당신 이 m 인 것을 볼 수 있습니다, 125 00:04:45,019 --> 00:04:48,505 그래서, 일종의에 이것을 넣어 갈거야 이 내 테이블 또는 내 바닥 인 경우 126 00:04:48,505 --> 00:04:50,650 나는 물건을 확산하고있어 병원을 나온 또는 내 배열 정말 - 127 00:04:50,650 --> 00:04:52,210 나는 거기에 미스를 모두 넣어 수 있습니다. 128 00:04:52,210 --> 00:04:52,710 오. 129 00:04:52,710 --> 00:04:55,020 여기 A. 그래서 나는 수도의 여기로했습니다. 130 00:04:55,020 --> 00:04:55,520 오. 131 00:04:55,520 --> 00:04:57,980 여기에 내가 갈거야 다른 A.이다 여기에 그것을 넣어. 132 00:04:57,980 --> 00:05:02,490 다음은 Z를 여기에 또 다른 M. 그래서입니다 이 같은 더미를 만들기 시작 수 있습니다. 133 00:05:02,490 --> 00:05:06,620 그리고 어쩌면 내가 나중에 갈 것 및 종류의 매우 nitpicky-LY 정렬 134 00:05:06,620 --> 00:05:07,710 개별 더미. 135 00:05:07,710 --> 00:05:11,300 그러나 요점은이 보일 것입니다 나는 손으로 해요 입력에서 136 00:05:11,300 --> 00:05:14,016 나는 약간의 계산 만들 것 그 입력에 기초하여 결정. 137 00:05:14,016 --> 00:05:15,640 그것이로 시작하면, 거기에 넣어. 138 00:05:15,640 --> 00:05:18,980 이 Z로 시작하면, 그것을 통해 넣어 사이에 존재하고, 모든 것을. 139 00:05:18,980 --> 00:05:22,730 >> 그래서이의 기술이다 일반적으로 hashing--의 H-A-S-H--로 알려진 140 00:05:22,730 --> 00:05:26,550 이는 일반적으로 복용 의미 입력과 계산이 입력을 사용하여 141 00:05:26,550 --> 00:05:30,940 값, 일반적으로 숫자, 그 번호는 저장에 대한 인덱스입니다 142 00:05:30,940 --> 00:05:32,260 컨테이너, 배열 등을들 수있다. 143 00:05:32,260 --> 00:05:35,490 그래서 다른 말로하면, 나는이있을 수 있습니다 해시 기능, 내 머리에서와 같이, 144 00:05:35,490 --> 00:05:37,940 내가 누군가의 보는 경우에 그 로 시작하는 이름, 145 00:05:37,940 --> 00:05:40,190 나는 그지도거야 내 머리 0으로. 146 00:05:40,190 --> 00:05:44,160 나는 Z와 사람을 볼 수 있다면, 난 내 머리 (25)에 그지도 것 147 00:05:44,160 --> 00:05:46,220 다음에 넣습니다 마지막으로 대부분의 더미. 148 00:05:46,220 --> 00:05:50,990 >> 이제, 경우에 당신은 내 뇌 없습니다 생각 그러나 C 프로그램, 어떤 번호가 있었던 149 00:05:50,990 --> 00:05:53,170 당신은 동일한 결과를 얻을 수에 의존? 150 00:05:53,170 --> 00:05:55,594 즉, 만약 , ASCII 문자 있었다 151 00:05:55,594 --> 00:05:57,510 당신은 어떻게 결정합니까 무엇 양동이에 넣어하는 방법? 152 00:05:57,510 --> 00:05:59,801 당신은 아마 싶지 않아 버킷 (65)에 넣어하는 153 00:05:59,801 --> 00:06:01,840 저기 같은 것 더 좋은 이유. 154 00:06:01,840 --> 00:06:04,320 어디를 넣어 싶어 그 ASCII 값의 측면에서? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 어디는 ASCII로 수행 할 작업 값은 스마트 버킷 가지고 올 157 00:06:08,920 --> 00:06:09,480 에 넣어하는 방법? 158 00:06:09,480 --> 00:06:10,206 >> 청중 : 마이너스 A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID 마란 : 그래. 160 00:06:10,956 --> 00:06:13,190 그래서 마이너스 마이너스 특히 65이 있다면 161 00:06:13,190 --> 00:06:18,240 자본 A. 98 경우 는 소문자입니다. 162 00:06:18,240 --> 00:06:21,300 그리고 그것은 매우, 우리를 할 수 있도록 할 간단하고 매우 산술적으로, 163 00:06:21,300 --> 00:06:23,260 그런 통에 넣어 뭔가. 164 00:06:23,260 --> 00:06:26,010 그래서 우리가 실제로 어떻게 밝혀 이뿐만 아니라 심지어 퀴즈. 165 00:06:26,010 --> 00:06:29,051 >> 그래서 당신은 당신이 원 불러올 수도있는 커버에 교육 동료의 이름입니다. 166 00:06:29,051 --> 00:06:32,270 그리고 TF의 이름이 조직되었다 알파벳이 컬럼에, 167 00:06:32,270 --> 00:06:34,400 물론, 믿거 나 말거나, 때 우리 모두 80 PLUS 168 00:06:34,400 --> 00:06:37,800 학년에 밤 함께있어 우리 그레이딩 공정의 마지막 단계 169 00:06:37,800 --> 00:06:41,830 큰에 퀴즈를 해시하는 것입니다 [들림] 바닥의 공간 170 00:06:41,830 --> 00:06:45,110 모두의 퀴즈를 배치하기 자신의 TF 년대 정확히 순서대로 171 00:06:45,110 --> 00:06:47,700 표지에 이름 때문에 그것은 우리에게 많은 쉽게 172 00:06:47,700 --> 00:06:51,290 그 사용하여 선형을 검색합니다 검색하거나 영리 어떤 종류의 173 00:06:51,290 --> 00:06:54,050 TF는 찾기위한 자신 그녀의 학생들의 퀴즈. 174 00:06:54,050 --> 00:06:56,060 >> 해싱의 그래서이 아이디어 당신은 볼 수 있음 175 00:06:56,060 --> 00:07:00,520 매우 강력 실제로 꽤 평범하고 매우 직관적, 176 00:07:00,520 --> 00:07:03,000 많은 아마도 나누어 추천하고 정복은 주 제로였다. 177 00:07:03,000 --> 00:07:05,250 핵킹 마라톤에 나는 빨리 감기 몇 년 전에. 178 00:07:05,250 --> 00:07:08,040 이 Zamyla과 몇했다 다른 직원 인사말 학생 179 00:07:08,040 --> 00:07:09,030 그들은 들어와. 180 00:07:09,030 --> 00:07:12,680 그리고 우리는 접는의 전체 무리가 있었다 이름 태그가 테이블. 181 00:07:12,680 --> 00:07:15,380 그리고 우리는 이름 태그를 구성했다 와 저기로 같은 182 00:07:15,380 --> 00:07:16,690 그리고 저기 ZS. 183 00:07:16,690 --> 00:07:20,350 그리고 TF들 중 하나 매우 영리하게 지침으로 쓴 184 00:07:20,350 --> 00:07:21,030 하루. 185 00:07:21,030 --> 00:07:24,480 그리고 학기이 12 주에 모든 완벽한 이해와 모든 사람을 만든 186 00:07:24,480 --> 00:07:25,310 무엇을 알고 있었다. 187 00:07:25,310 --> 00:07:27,900 그러나 언제 당신은했습니다 동일한 방식으로 대기, 188 00:07:27,900 --> 00:07:30,272 당신을 구현하고 해시 같은 개념. 189 00:07:30,272 --> 00:07:31,730 그래서이 조금 공식화 할 수 있습니다. 190 00:07:31,730 --> 00:07:32,890 다음은 배열입니다. 191 00:07:32,890 --> 00:07:36,820 그것은 조금 수 그려 넓은 단지 시각적으로 묘사하기 위해, 192 00:07:36,820 --> 00:07:38,920 우리는 문자열을 넣을 수 있음 이 같은 뭔가. 193 00:07:38,920 --> 00:07:41,970 그리고이 배열이다 명확하게 크기 26 총. 194 00:07:41,970 --> 00:07:43,935 그리고 일이 호출됩니다 테이블 임의로. 195 00:07:43,935 --> 00:07:48,930 그러나 이것은 단지 작가의 연주입니다 해시 테이블이 될 일의. 196 00:07:48,930 --> 00:07:52,799 >> 그래서 해시 테이블은 지금에 가고 더 높은 레벨 데이터 구조 일. 197 00:07:52,799 --> 00:07:54,840 하루의 끝에서 우리는 당신이 볼 것을 대략 198 00:07:54,840 --> 00:07:58,700 해시 테이블을 구현할 수있는 많은 체크인 라인처럼 199 00:07:58,700 --> 00:08:02,059 많은 이런 핵킹 마라톤에서 표는 시험 책을 정렬에 사용. 200 00:08:02,059 --> 00:08:03,850 그러나 해시 테이블이고 이러한 높은 수준의 종류 201 00:08:03,850 --> 00:08:08,250 배열을 사용할 수 개념 후드가 그것을 구현하는 아래 202 00:08:08,250 --> 00:08:11,890 아니면 길이리스트를 사용, 또는 심지어 수 아마도 일부 다른 데이터 구조. 203 00:08:11,890 --> 00:08:15,590 그리고 지금은 theme-- 복용 이러한 기본적인 성분의 일부 204 00:08:15,590 --> 00:08:18,310 배열이 건물 등 길이 목록의 현재 차단 205 00:08:18,310 --> 00:08:21,740 우리가 구축 할 수있는 다른 무엇을보고 그 위에, 재료 등 206 00:08:21,740 --> 00:08:26,550 조리법에 더 많은을 재미 있고 유용한 최종 결과. 207 00:08:26,550 --> 00:08:28,680 >> 해시 테이블에 따라서 우리는 그것을 구현할 수 208 00:08:28,680 --> 00:08:32,540 메모리에 그림으로이 같은,하지만 어떻게 실제로 최대 코딩 할 수 있습니까? 209 00:08:32,540 --> 00:08:33,789 글쎄, 단순히 이것이다. 210 00:08:33,789 --> 00:08:38,270 모두 대문자로 용량이 단지 인 경우 예 (26)에 대한 몇 가지 constant--, 211 00:08:38,270 --> 00:08:42,030 alphabet--의 26 글자에 대한 내 변수 테이블을 호출 할 수 있습니다, 212 00:08:42,030 --> 00:08:45,630 그리고 내가 갈거야 주장 할 수 거기에, 또는 문자열에 문자 별을 넣어. 213 00:08:45,630 --> 00:08:49,880 그래서 간단합니다 경우이 같이 해시 테이블을 구현하려는. 214 00:08:49,880 --> 00:08:51,490 그럼에도 불구하고,이 정말 그냥 배열입니다. 215 00:08:51,490 --> 00:08:53,198 그러나 다시, 해시 표는 우리가거야 지금 216 00:08:53,198 --> 00:08:57,470 단지 추상적 인 데이터 타입을 호출 상단에 레이어 개념의 종류 217 00:08:57,470 --> 00:09:00,780 더 평범한 무언가의 이제 배열을 좋아한다. 218 00:09:00,780 --> 00:09:02,960 >> 이제, 우리가 어떻게 이동합니까 문제 해결에 대한? 219 00:09:02,960 --> 00:09:06,980 음, 이전에 내가 사치를했다 의 여기에 충분한 테이블 공간을 가진 220 00:09:06,980 --> 00:09:09,460 나는 넣을 수 있도록 퀴즈 어디서나 내가 원했다. 221 00:09:09,460 --> 00:09:10,620 그래서으로는 여기 있습니다. 222 00:09:10,620 --> 00:09:12,100 ZS는 여기 있습니다. 223 00:09:12,100 --> 00:09:13,230 MS는 여기 있습니다. 224 00:09:13,230 --> 00:09:14,740 그리고 나는 약간의 여분의 공간이 있었다. 225 00:09:14,740 --> 00:09:18,740 그러나 이것은 속임수 권리의 비트입니다 지금이 테이블 때문에, 내가하면 정말 226 00:09:18,740 --> 00:09:22,720 배열로 생각, 그냥 어떤 고정 된 크기가 될 것. 227 00:09:22,720 --> 00:09:25,380 >> 그래서 기술적으로, 나는 당기면 다른 학생의 퀴즈까지 228 00:09:25,380 --> 00:09:28,490 이 사람의, 오, 참조 이름은 너무 시작 229 00:09:28,490 --> 00:09:30,980 나는 종류의 거기를 넣을. 230 00:09:30,980 --> 00:09:34,740 그러나 곧 나는 경우, 거기 넣어 이 테이블은 실제로 배열을 나타냅니다, 231 00:09:34,740 --> 00:09:37,840 나는 무시하거나 건드리지 될거야 누구든지이 학생의 퀴즈입니다. 232 00:09:37,840 --> 00:09:38,340 오른쪽? 233 00:09:38,340 --> 00:09:41,972 이러한 배열의 경우, 단 하나가 수 이러한 세포의 각 요소에 이동합니다. 234 00:09:41,972 --> 00:09:43,680 그래서 나는 가지가 선택하고 선택합니다. 235 00:09:43,680 --> 00:09:45,735 >> 이제 이전의 내가 가지 사기 및이 아니면했다 236 00:09:45,735 --> 00:09:47,526 단지 종류의 적층 서로 위의 그들. 237 00:09:47,526 --> 00:09:49,170 하지만 그 코드에 비행 않을거야. 238 00:09:49,170 --> 00:09:52,260 그래서 어디를 넣을 수 이름이 두 번째 학생 239 00:09:52,260 --> 00:09:54,964 내가 가진 모든이 경우 A는 사용 가능한 테이블 공간? 240 00:09:54,964 --> 00:09:57,880 그리고 3 개의 슬롯과 ​​사용했습니다 몇 가지 다른 사람들이있는 것 같다. 241 00:09:57,880 --> 00:09:58,959 당신은 무엇을 할 수 있을까? 242 00:09:58,959 --> 00:09:59,834 청중 : [들리지] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID 마란 : 그래. 245 00:10:01,315 --> 00:10:02,370 어쩌면 그냥 간단하게 할 수 있습니다. 246 00:10:02,370 --> 00:10:02,660 오른쪽? 247 00:10:02,660 --> 00:10:04,243 나는 그것을 넣을 곳은 적합하지 않습니다. 248 00:10:04,243 --> 00:10:07,450 그래서 넣어 갈거야 기술적으로 B가 갈 것입니다 경우. 249 00:10:07,450 --> 00:10:09,932 지금, 물론, 내가 시작 해요 코너에 자신을 페인트. 250 00:10:09,932 --> 00:10:11,890 나는 학생에 도착하면 이름이 실제로는 B이다, 251 00:10:11,890 --> 00:10:14,840 이제 B는 조금 이동 될 것입니다 앞으로, 등, 네, 일어날 수 252 00:10:14,840 --> 00:10:17,530 이 B 인 경우, 지금은 여기에있다. 253 00:10:17,530 --> 00:10:20,180 >> 그래서이 매우 빠르게 , 문제가 될 수 254 00:10:20,180 --> 00:10:23,850 하지만, 기술은 실제로 야 선형 프로빙라고, 255 00:10:23,850 --> 00:10:26,650 이에 방금 고려하여 배열은 라인을 따라합니다. 256 00:10:26,650 --> 00:10:29,680 그리고 당신이 종류의 조사 또는 사용 가능한 각 요소를 검사 257 00:10:29,680 --> 00:10:31,360 사용 가능한 자리를 찾고. 258 00:10:31,360 --> 00:10:34,010 그리고 가능한 빨리 발견하면 하나는, 당신은 거기에 놓습니다. 259 00:10:34,010 --> 00:10:38,390 >> 이제, 가격은 현재 지불되고 이 솔루션은 무엇입니까? 260 00:10:38,390 --> 00:10:41,300 우리는 고정 된 크기 어레이가, 나는 이름을 삽입 할 때 261 00:10:41,300 --> 00:10:44,059 그것으로, 적어도 처음, 무엇이다 삽입의 실행 시간 262 00:10:44,059 --> 00:10:46,350 학생들을 '퍼팅 오른쪽 양동이에 퀴즈? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 무슨 큰 O? 265 00:10:50,002 --> 00:10:51,147 >> 청중 : N. 266 00:10:51,147 --> 00:10:52,480 DAVID 마란 : 나는 N의 큰 O를 들었다. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 사실이 아닙니다. 269 00:10:54,300 --> 00:10:56,490 그러나 우리는 떨어져 애타게 것 왜 그냥 순간에. 270 00:10:56,490 --> 00:10:57,702 그것은 다른 무엇을 할 수 있는가? 271 00:10:57,702 --> 00:10:58,755 >> 청중 : [들리지] 272 00:10:58,755 --> 00:11:00,380 DAVID 마란 : 그리고 저를 시각적으로 할 수 있습니다. 273 00:11:00,380 --> 00:11:04,720 그래서이 편지 S.은 가정하자 274 00:11:04,720 --> 00:11:05,604 >> 청중 : 그것은 하나입니다. 275 00:11:05,604 --> 00:11:06,520 DAVID 마란 : 그것은 하나입니다. 276 00:11:06,520 --> 00:11:06,710 오른쪽? 277 00:11:06,710 --> 00:11:08,950 이 배열 인 우리는 랜덤 액세스를 의미합니다. 278 00:11:08,950 --> 00:11:11,790 그리고 우리는이 생각한다면 제로이 같은 25, 279 00:11:11,790 --> 00:11:13,800 우리는 그 실현, 아, 여기 내 입력 S가이다, 280 00:11:13,800 --> 00:11:16,350 나는 확실히 변환 할 수 있습니다 S, ASCII 문자, 281 00:11:16,350 --> 00:11:18,540 해당 번호에 영 ~ 25 282 00:11:18,540 --> 00:11:20,910 다음 바로 자신이 속한 곳을 넣습니다. 283 00:11:20,910 --> 00:11:26,120 >> 그러나 물론, 최대한 빨리는 도착으로 이름의 두 번째 사람은 A 또는 B 또는 C이다 284 00:11:26,120 --> 00:11:29,300 결국, 내가 사용했을 경우 선형, 내 솔루션으로 프로빙 285 00:11:29,300 --> 00:11:31,360 의 실행 시간 최악의 경우 삽입 286 00:11:31,360 --> 00:11:33,120 실제로 무엇으로 바뀔 것입니다? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 그리고 난 여기가 되셨습니까 제대로 초기에. 289 00:11:36,045 --> 00:11:36,920 청중 : [들리지] 290 00:11:36,920 --> 00:11:41,620 DAVID 마란 : 그래서 그것은 참 한번 n은 당신은 충분히 큰 데이터 세트를 가지고있다. 291 00:11:41,620 --> 00:11:44,410 따라서, 한편으로, 만약 당신의 배열이 충분한 크기 292 00:11:44,410 --> 00:11:48,287 당신의 데이터는 당신은 충분히 스파 스 이 아름다운 일정 시간을 얻을. 293 00:11:48,287 --> 00:11:50,620 그러나 곧 시작으로 점점 더 많은 요소를 얻고, 294 00:11:50,620 --> 00:11:53,200 다만 통계적으로 당신은 얻을 문자로 더 많은 사람들이 295 00:11:53,200 --> 00:11:56,030 그들의 이름 또는 편지 B, 잠재적으로 수 296 00:11:56,030 --> 00:11:57,900 뭔가 더 선형으로 바뀔. 297 00:11:57,900 --> 00:11:59,640 그래서 아주 완벽하지. 298 00:11:59,640 --> 00:12:00,690 그래서 우리는 더 잘 발음 할 수 있나요? 299 00:12:00,690 --> 00:12:03,210 >> 그럼,이었다 우리의 솔루션 때를하기 전에 300 00:12:03,210 --> 00:12:06,820 보다 더 역 동성을 갖고 싶어 배열과 같은 허용? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 청중 : [들리지] 303 00:12:08,960 --> 00:12:10,030 DAVID 마란 : 우리는 무엇을 소개 했습니까? 304 00:12:10,030 --> 00:12:10,530 그래. 305 00:12:10,530 --> 00:12:11,430 그래서 연결리스트. 306 00:12:11,430 --> 00:12:14,430 음,이 링크 해 보자 목록 대신 우리를 위해 할 수 있습니다. 307 00:12:14,430 --> 00:12:17,630 글쎄, 내가 그 우리를 제안하자 다음과 같이 그림을 그립니다. 308 00:12:17,630 --> 00:12:19,620 지금 이것은 다른 예로부터 그림 309 00:12:19,620 --> 00:12:24,750 다른 텍스트에서, 실제로 그 실제로 크기 (31)의 배열을 사용한다. 310 00:12:24,750 --> 00:12:28,220 그리고이 저자 단순히 문자열을 해시로 결정 311 00:12:28,220 --> 00:12:32,430 그 사람의 이름을 기반으로하지, 하지만 자신의 생년월일에 따라. 312 00:12:32,430 --> 00:12:35,680 에 관계없이 월, 그들은 생각 당신은 한 달의 1 일에 태어난하는 경우 313 00:12:35,680 --> 00:12:39,580 또는 그 달의 31 일, 저자 그 값에 기초하여 해싱 것 314 00:12:39,580 --> 00:12:44,154 비트로부터 이름을 확산 시키도록 다만 26 점을 허용하는 것보다 더. 315 00:12:44,154 --> 00:12:47,320 그리고 아마도 좀 더 균일 한이다 알파벳 문자로가는 것보다, 316 00:12:47,320 --> 00:12:50,236 때문에 물론 거기에 아마 이름으로 세계에 더 많은 사람들이 317 00:12:50,236 --> 00:12:54,020 확실히 이상으로 그 시작 알파벳의 다른 글자. 318 00:12:54,020 --> 00:12:56,380 아마이 조금이다 보다 균일 한, 가정 319 00:12:56,380 --> 00:12:58,640 균일 한 분포 한 달에 걸쳐 아기의. 320 00:12:58,640 --> 00:12:59,990 >> 그러나 물론, 이것은 여전히​​ 불완전하다. 321 00:12:59,990 --> 00:13:00,370 오른쪽? 322 00:13:00,370 --> 00:13:01,370 우리는 충돌을 데있어. 323 00:13:01,370 --> 00:13:04,680 이에있는 여러 사람들 데이터 구조는 여전히 324 00:13:04,680 --> 00:13:08,432 적어도 동일한 생년월일을 갖는 당신은 한달에 관계없이 것입니다. 325 00:13:08,432 --> 00:13:09,640 그러나 저자는 무엇을했다? 326 00:13:09,640 --> 00:13:13,427 우리가 배열을 가지고있는 것처럼 보이네요 수직으로 그려진 왼쪽에, 327 00:13:13,427 --> 00:13:15,010 하지만 그것은 단지 작가의 연주입니다. 328 00:13:15,010 --> 00:13:18,009 그것은 중요하지 않습니다 어떤 방향을 배열을 그려, 여전히 배열입니다. 329 00:13:18,009 --> 00:13:20,225 이런 방식이 배열 무엇입니까? 330 00:13:20,225 --> 00:13:21,500 >> 청중 : 링크 된 목록입니다. 331 00:13:21,500 --> 00:13:21,650 >> DAVID 마란 : 그래. 332 00:13:21,650 --> 00:13:23,490 가있어 것 같습니다 연결리스트의 배열입니다. 333 00:13:23,490 --> 00:13:26,490 그래서 다시, 종류의이 시점에 이제 이러한 데이터 구조를 이용하는 334 00:13:26,490 --> 00:13:28,550 이상으로 성분으로 흥미로운 솔루션, 335 00:13:28,550 --> 00:13:30,862 당신은 절대적으로 걸릴 수 있습니다 기본적인 배열과 같은, 336 00:13:30,862 --> 00:13:33,320 다음 뭔가 더 걸릴 링크리스트와 같은 재미있는 337 00:13:33,320 --> 00:13:36,660 심지어 더로 결합 더 흥미로운 데이터 구조. 338 00:13:36,660 --> 00:13:39,630 그리고 실제로,이 너무 것 해시 테이블을 호출, 339 00:13:39,630 --> 00:13:42,610 이에 배열 인 정말로 해시 테이블, 340 00:13:42,610 --> 00:13:45,600 하지만 해시 테이블에는 체인은, 그래서, 말하자면 341 00:13:45,600 --> 00:13:50,220 그 성장하거나에 따라 수축 요소의 수는 당신이 삽입 할. 342 00:13:50,220 --> 00:13:52,990 >> 이제, 따라서, 무엇이다 지금 시간을 실행? 343 00:13:52,990 --> 00:13:58,030 나는 누군가를 삽입 할 경우 10월 31일 누구의 생일이다, 344 00:13:58,030 --> 00:13:59,040 어디 그 또는 그녀는 가는가? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 좋아. 347 00:14:01,030 --> 00:14:02,819 이 31라는 매우 하단에서. 348 00:14:02,819 --> 00:14:03,610 그리고 완벽 해. 349 00:14:03,610 --> 00:14:05,060 즉 일정 시간이었다. 350 00:14:05,060 --> 00:14:08,760 그러나 우리는 다른 사람을 찾을 경우 누구의 생일, 보자되어, 351 00:14:08,760 --> 00:14:10,950 10 월, 11 년 12 월 31 일? 352 00:14:10,950 --> 00:14:12,790 어디 그 또는 그녀는 갈거야? 353 00:14:12,790 --> 00:14:13,290 같은 일. 354 00:14:13,290 --> 00:14:13,970 하지만 두 단계. 355 00:14:13,970 --> 00:14:15,303 즉, 비록 일정하지 않습니다? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 좋아. 358 00:14:16,860 --> 00:14:17,840 순간 그 것이다. 359 00:14:17,840 --> 00:14:20,570 그러나, 일반적인 경우에, 우리가 추가 더 많은 사람들, 360 00:14:20,570 --> 00:14:23,790 확률 적으로, 우리는거야 더 많은 충돌을 얻을 수 있습니다. 361 00:14:23,790 --> 00:14:26,820 >> 지금 이것은 조금이다 더 나은 기술적 때문에 362 00:14:26,820 --> 00:14:34,580 지금 내 체인에있을 수 최악의 경우 얼마나 오래? 363 00:14:34,580 --> 00:14:38,890 나는이 더에 N 사람을 삽입하는 경우 복잡한 데이터 구조, N 사람, 364 00:14:38,890 --> 00:14:41,080 최악의 경우는 N 될 것. 365 00:14:41,080 --> 00:14:41,815 왜? 366 00:14:41,815 --> 00:14:43,332 >> 청중 : 때문에 경우 모두 같은 생일을 가지고, 367 00:14:43,332 --> 00:14:44,545 그들은 한 줄이 될 것입니다. 368 00:14:44,545 --> 00:14:45,420 DAVID 마란 : 완벽한. 369 00:14:45,420 --> 00:14:47,480 그것은, 약간의 인위적인 수 있습니다 그러나 진정 최악의 경우, 370 00:14:47,480 --> 00:14:50,117 모두가 같은 생일이있는 경우, 당신이 가지고있는 입력 주어, 371 00:14:50,117 --> 00:14:51,950 당신은이 겁니다 대규모 긴 체인. 372 00:14:51,950 --> 00:14:54,241 그래서, 당신은 그것을 호출 할 수 있습니다 테이블을 해시,하지만 정말입니다 373 00:14:54,241 --> 00:14:56,810 그냥 대규모 연결리스트 낭비되는 공간의 전체를 많이. 374 00:14:56,810 --> 00:15:00,460 그러나 일반적으로, 우리가 가정하는 경우 적어도 생일 uniform-- 있습니다 375 00:15:00,460 --> 00:15:01,750 그리고 그것은 그렇지 않다. 376 00:15:01,750 --> 00:15:02,587 나는 그를 만들고있어. 377 00:15:02,587 --> 00:15:04,420 그러나 우리는 가정하면, 대한 토론을 위해 378 00:15:04,420 --> 00:15:07,717 그들은 다음 이론, 경우 있음 이 수직 표현 379 00:15:07,717 --> 00:15:11,050 배열의 잘 잘하면 당신이있어 , 당신이 알고 사슬을 얻을 것, 380 00:15:11,050 --> 00:15:15,880 거의 같은 길이 어디에 각 이 달의 날을 나타냅니다. 381 00:15:15,880 --> 00:15:19,930 >> 달에 삼십일일이 있다면 지금, 정말 내 실행 시간을 의미 382 00:15:19,930 --> 00:15:25,230 (31)를 통해 N의 큰 O는, 인 선형보다 더 느낀다. 383 00:15:25,230 --> 00:15:27,950 그러나 한 것이었다 우리 약속 몇 주 384 00:15:27,950 --> 00:15:31,145 전은 표현에 와서 때마다 알고리즘의 실행 시간은? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 그냥 만 높은 순서 기간을 확인합니다. 387 00:15:35,190 --> 00:15:35,690 오른쪽? 388 00:15:35,690 --> 00:15:37,400 31 확실히 도움이됩니다. 389 00:15:37,400 --> 00:15:39,610 그러나 이것은 여전히​​ N의 큰 O입니다. 390 00:15:39,610 --> 00:15:41,730 그러나 테마 중 하나 의 문제는 다섯 설정 391 00:15:41,730 --> 00:15:43,950 로 될 것입니다 절대적으로 그 인정, 392 00:15:43,950 --> 00:15:47,320 점근 적, 이론적으로 데이터 구조 393 00:15:47,320 --> 00:15:50,470 단지보다 낫다 하나의 거대한 연결리스트. 394 00:15:50,470 --> 00:15:53,550 그리고 실제로, 최악의 경우,이 해시 테이블은으로 바뀔 수 있습니다. 395 00:15:53,550 --> 00:15:57,620 >> 그러나 현실 세계에서 우리와 함께 인간 자신의 맥 또는 PC 나 어떤 그 396 00:15:57,620 --> 00:16:01,240 그리고 현실 세계를 실행하는 실제 데이터의 소프트웨어, 397 00:16:01,240 --> 00:16:03,260 어떤 알고리즘 당신이 선호하는 건가요? 398 00:16:03,260 --> 00:16:09,180 최종 단계 또는 소요 하나 N 31 단계로 나누어 소요 하나 399 00:16:09,180 --> 00:16:12,900 데이터의 일부 조각을 찾거나 몇 가지 정보를 찾기 위해? 400 00:16:12,900 --> 00:16:16,580 나는 절대적으로 31 차종을 의미 현실 세계에서의 차이. 401 00:16:16,580 --> 00:16:18,540 그것은 31 배 빠른 속도입니다. 402 00:16:18,540 --> 00:16:20,880 그리고 우리 인간은 확실히 있습니다 그 감사 것. 403 00:16:20,880 --> 00:16:23,004 >> 그래서 이분법을 실현 이 실제로 사이 404 00:16:23,004 --> 00:16:25,920 이론적으로 것들에 대해 이야기 확실히 및 점근하는 405 00:16:25,920 --> 00:16:28,760 우리가 보았 듯이 값을 가지고, 그러나 현실 세계에서, 406 00:16:28,760 --> 00:16:32,930 당신은 단지을 걱정하는 경우 일반 입력에 대한 인간의 행복, 407 00:16:32,930 --> 00:16:36,010 당신은 매우 잘 읽고 동의를 할 수 있습니다 예,이 선형, 사실, 408 00:16:36,010 --> 00:16:38,360 하지만 31 배 빠른 속도이다 보다 선형이 될 수 있습니다. 409 00:16:38,360 --> 00:16:41,610 그리고 더 나은 아직, 우리는 필요가 없습니다 생년월일 같은 임의의 일을, 410 00:16:41,610 --> 00:16:44,030 우리는 조금 보낼 수 더 많은 시간과 영리함 411 00:16:44,030 --> 00:16:47,140 우리가 할 수있는 일에 대해 생각, 주어진 사람의 이름과 아마 412 00:16:47,140 --> 00:16:50,130 자신의 생년월일은 사람들을 결합 성분은 무엇인가를 알아 내기 위해 413 00:16:50,130 --> 00:16:52,720 즉 진정으로 더 균일하고 적은 톱니, 414 00:16:52,720 --> 00:16:56,250 그래서이 그림보다 이야기하기 현재이 될 수 있습니다 제안합니다. 415 00:16:56,250 --> 00:16:57,750 우리는 어떻게 코드에서이를 구현할 수있다? 416 00:16:57,750 --> 00:17:00,280 글쎄, 내가 그 우리를 제안하자 우리가했습니다 몇 가지 구문을 빌려 417 00:17:00,280 --> 00:17:01,799 지금까지 몇 번을 사용했다. 418 00:17:01,799 --> 00:17:03,590 그리고 내가 정의하는거야 노드, 이는 다시 419 00:17:03,590 --> 00:17:06,812 단지 일부에 대한 일반적인 용어이다 일부 데이터 구조에 대한 컨테이​​너입니다. 420 00:17:06,812 --> 00:17:09,020 나는 그 제안거야 문자열은 거기에 것입니다. 421 00:17:09,020 --> 00:17:11,369 그러나 우리는 복용 시작하는거야 지금 떨어져 바퀴를 훈련하는. 422 00:17:11,369 --> 00:17:13,230 >> 더 이상 CS50 라이브러리 없다 정말, 당신이 원하는하지 않는 한 423 00:17:13,230 --> 00:17:15,230 최종을 위해 사용하는 괜찮 프로젝트, 424 00:17:15,230 --> 00:17:18,569 그러나 지금 우리는 철수거야 커튼과 그냥 문자 스타 말할. 425 00:17:18,569 --> 00:17:22,069 단어 그래서이 될 것입니다 본인의 이름. 426 00:17:22,069 --> 00:17:25,079 그리고 지금은 링크가 여기에서 다음 노드로 427 00:17:25,079 --> 00:17:28,170 이 대표 있도록 각 노드 428 00:17:28,170 --> 00:17:30,950 체인, 잠재적 연결리스트의. 429 00:17:30,950 --> 00:17:34,090 >> 그리고 지금은 어떻게 선언 할 해시 테이블 자체? 430 00:17:34,090 --> 00:17:36,660 어떻게하면이 전체 구조를 선언합니까? 431 00:17:36,660 --> 00:17:40,960 음, 정말, 많이 나는 포인터를 사용처럼 목록의 바로 첫 번째 요소 432 00:17:40,960 --> 00:17:44,510 전에, 마찬가지로 난 그냥 말할 수 난 그냥 포인터의 무리가 필요 433 00:17:44,510 --> 00:17:46,270 이 모든 해시 테이블을 구현합니다. 434 00:17:46,270 --> 00:17:49,484 나는 배열을거야 해시 테이블이라는 테이블. 435 00:17:49,484 --> 00:17:50,900 그것은 크기의 용량이 될 것. 436 00:17:50,900 --> 00:17:52,525 즉,에 들어갈 수있는 방법을 많은 요소입니다. 437 00:17:52,525 --> 00:17:56,180 그리고이에 그 각 요소 배열은 노드 스타가 될 것입니다. 438 00:17:56,180 --> 00:17:56,810 왜? 439 00:17:56,810 --> 00:18:00,160 음,이 그림 당, 내가 뭘 해요 해시 테이블로서 구현 440 00:18:00,160 --> 00:18:04,330 효과적으로에 시작은 그냥 우리가 수직으로 그려 한이 배열, 441 00:18:04,330 --> 00:18:06,820 그 사각형의 각 포인터를 나타냅니다. 442 00:18:06,820 --> 00:18:09,170 사람은 슬래시를 가지고 있고, 그들을 통해 단지 null입니다. 443 00:18:09,170 --> 00:18:11,410 그리고 사람은 그이 오른쪽에가는 화살표 444 00:18:11,410 --> 00:18:16,140 실제 노드 실제 포인터이고, 연결리스트의 시작을 ERGO. 445 00:18:16,140 --> 00:18:19,050 >> 그래서 여기, 다음, 우리가 어떻게 힘이다 해시 테이블을 구현하는 446 00:18:19,050 --> 00:18:21,580 별도의 체인을 구현한다. 447 00:18:21,580 --> 00:18:22,840 이제 우리는 더 잘 할 수 있습니까? 448 00:18:22,840 --> 00:18:25,632 좋아 나는 지난 시간에 약속이 우리는 일정 시간을 달성 할 수있다. 449 00:18:25,632 --> 00:18:27,381 그리고 나는 종류의 준 여기에 일정 시간, 450 00:18:27,381 --> 00:18:29,850 하지만 정말로 말했다 일정 시간이 여전히 있기 때문에 451 00:18:29,850 --> 00:18:31,890 총에 의존 요소 수 452 00:18:31,890 --> 00:18:34,500 당신은에 입력하고 데이터 구조. 453 00:18:34,500 --> 00:18:35,980 그러나 우리는 이런 짓을 가정합니다. 454 00:18:35,980 --> 00:18:39,550 내가 여기에 화면으로 돌아 가자. 455 00:18:39,550 --> 00:18:44,520 나 또한 여기를 프로젝트 명확한하자 화면이, 내가 이런 짓을 가정합니다. 456 00:18:44,520 --> 00:18:49,300 내가 이름을 삽입하고 싶어한다고 가정 데 이븐 내 데이터 구조에. 457 00:18:49,300 --> 00:18:52,100 >> 그래서 문자열을 삽입 할 데이터 구조로 데 이븐. 458 00:18:52,100 --> 00:18:54,370 내가 사용하지 않는 경우 테이블을 해시,하지만 난 사용 459 00:18:54,370 --> 00:18:56,980 더 뭔가 나무와 같은 가족 나무처럼 460 00:18:56,980 --> 00:18:59,670 당신은에 어떤 루트를 상단과 다음 노드와 잎 461 00:18:59,670 --> 00:19:01,440 그 아래쪽과 바깥쪽으로 이동합니다. 462 00:19:01,440 --> 00:19:04,450 , 그 I를 가정 데 이븐의를 삽입 할 463 00:19:04,450 --> 00:19:06,430 현재 빈리스트 무엇으로. 464 00:19:06,430 --> 00:19:09,780 나는 다음과 같은 작업을 수행 할거야 : 난 이 가족의 노드를 만들 것 465 00:19:09,780 --> 00:19:15,170 나무와 같은 데이터 구조 보인다 조금이 같은, 각각의 466 00:19:15,170 --> 00:19:19,640 사각형은,,의 말을 할 수있다 그것은 지금 26 요소. 467 00:19:19,640 --> 00:19:21,650 그리고 각 셀 이 배열 것입니다 468 00:19:21,650 --> 00:19:23,470 알파벳의 문자를 나타냅니다. 469 00:19:23,470 --> 00:19:28,190 >> 특히, 나는 치료하는거야 이것은, 다음, B, C 다음, 다음 D이다 470 00:19:28,190 --> 00:19:29,310 여기 하나. 471 00:19:29,310 --> 00:19:32,940 그래서이 효과적으로 것입니다 문자 디를 나타냅니다 472 00:19:32,940 --> 00:19:36,040 그러나 데 이븐의 모든 삽입 내가 좀 더해야 할 이름을 지정합니다. 473 00:19:36,040 --> 00:19:37,840 그래서 내가 먼저 말하자면, 해시에 갈거야. 474 00:19:37,840 --> 00:19:41,049 나는 첫 번째 문자를보고 갈거야 의 데 이븐의 분명 D 인 475 00:19:41,049 --> 00:19:42,840 나는 할당 할거야 보이는 노드 476 00:19:42,840 --> 00:19:45,570 같은 큰 큰 사각형을 두도록 전체 알파벳 맞게 충분히. 477 00:19:45,570 --> 00:19:47,140 >> 이제 D가 이루어집니다. 478 00:19:47,140 --> 00:19:49,720 이제 A. D-A-V-E-N이 목표입니다. 479 00:19:49,720 --> 00:19:51,220 그래서 지금 내가 할거야 무슨이이다. 480 00:19:51,220 --> 00:19:54,027 최대한 빨리 D 통지를 시작으로 거기에는 포인터가 없습니다. 481 00:19:54,027 --> 00:19:56,860 그것은 순간에 쓰레기 값을의 아니면 null로 초기화 할 수 있습니다. 482 00:19:56,860 --> 00:19:59,630 그러나 저와 계속하자 나무를 구축하는이 아이디어. 483 00:19:59,630 --> 00:20:04,260 날이 또 다른 하나를 할당하자 그것은 26 요소가 노드. 484 00:20:04,260 --> 00:20:05,150 >> 그리고 당신이 뭘 알아? 485 00:20:05,150 --> 00:20:09,130 이 메모리에 단지 노드 인 경우 그 나는 구조체를 사용하여, malloc을 사용하여 만든 486 00:20:09,130 --> 00:20:11,240 우리는 곧 살펴 보 겠지만, 나는 이런것을 할거야 487 00:20:11,240 --> 00:20:14,450 나는에서 화살표를 그릴거야 아래 D를 나타내는 것 488 00:20:14,450 --> 00:20:15,860 이 새로운 노드. 489 00:20:15,860 --> 00:20:19,240 그리고, 제 다음 지금 데 이븐의 이름으로 편지, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- 나는 앞서 갈거야 이 같은 다른 노드를 그릴, 491 00:20:24,150 --> 00:20:30,150 이에, 여기에 V 요소, 어떤 우리는 instance-- 으악 그려 주께. 492 00:20:30,150 --> 00:20:31,020 우리가 그리하지 않습니다. 493 00:20:31,020 --> 00:20:31,936 여기 갈 것입니다. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> 그럼 우리가가는거야 이 V.이라고 생각 496 00:20:35,712 --> 00:20:44,920 그리고 여기있는 우리는 색인에 갈거야 아래 V에서 우리가 E. 고려해 볼게 무엇에 497 00:20:44,920 --> 00:20:50,100 그리고 여기에서 우리는에 갈거야 여기에 이​​러한 노드 중 하나가 이동합니다. 498 00:20:50,100 --> 00:20:52,930 그리고 지금 우리는 대답 할 수있는 질문이 있습니다. 499 00:20:52,930 --> 00:20:57,840 나는 것을 나타냅니다 어떻게 든 필요 우리는 문자열 데 이븐의 끝에있어. 500 00:20:57,840 --> 00:20:59,490 그래서 난 그냥 널 떠날 수 있습니다. 501 00:20:59,490 --> 00:21:02,670 >> 그러나 우리는 데 이븐의 무엇이있는 경우 또한 전체 이름, 어떤 502 00:21:02,670 --> 00:21:04,280 우리가, 데븐 포트 말했듯이, 무엇입니까? 503 00:21:04,280 --> 00:21:06,970 그래서 데 이븐은 무엇입니까 실제로 문자열, 504 00:21:06,970 --> 00:21:08,960 더 이상 문자열의 접두사? 505 00:21:08,960 --> 00:21:11,450 우리는 영구적으로 할 수 없습니다 아무것도 진행하지 말 506 00:21:11,450 --> 00:21:14,410 때문에 우리가 할 수, 거기에 가고 데븐 포트와 같은 단어를 삽입하지 마십시오 507 00:21:14,410 --> 00:21:15,840 이 데이터 구조에 508 00:21:15,840 --> 00:21:19,560 >> 그래서 우리는 무엇을 할 수 있는지 대신하다 이들 요소의 각각을 치료 509 00:21:19,560 --> 00:21:22,170 같은 어쩌면 두 가지는 그들 내부의 요소. 510 00:21:22,170 --> 00:21:24,810 하나는, 참으로, 포인터 나는이 일을했습니다. 511 00:21:24,810 --> 00:21:27,100 이 상자의 각 그래서 하나의 세포가 아닙니다. 512 00:21:27,100 --> 00:21:29,855 그러나 경우 최고 보이면 아래 하나의 513 00:21:29,855 --> 00:21:32,230 때문에, 널 (null)이 될 것 아직 더 대븐 포트가 없습니다. 514 00:21:32,230 --> 00:21:34,197 어떤 경우 상단 하나 특별한 가치인가? 515 00:21:34,197 --> 00:21:36,530 그리고 그것은 조금 될 것 그것은이 크기 그릴 하드. 516 00:21:36,530 --> 00:21:38,130 하지만 그냥 체크 마크의 가정. 517 00:21:38,130 --> 00:21:38,920 확인합니다. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N은 문자열입니다 이 데이터 구조. 519 00:21:44,230 --> 00:21:48,350 >> 한편, 경우에 나는 더 많은 공간이 있었다 여기에, 나는, P-O-R-T를 할 수 520 00:21:48,350 --> 00:21:52,650 나는 노드에 체크를 넣을 수 즉, 맨 마지막에 편지 T가 있습니다. 521 00:21:52,650 --> 00:21:55,460 그래서이 대규모입니다 복잡한 수준의 데이터 구조를. 522 00:21:55,460 --> 00:21:57,210 그리고 내 필기 확실히 도움이되지 않습니다. 523 00:21:57,210 --> 00:22:00,043 하지만 뭔가를 삽입하기를 원한다면 또, 우리가 무엇을 할 것이라고 생각. 524 00:22:00,043 --> 00:22:03,370 우리가 다윗을 넣어 원하는 경우, 우리는 같은 논리, D-A-V를 따라 줄 525 00:22:03,370 --> 00:22:08,802 하지만 지금은 다음에 가리키는 것 요소하지 E에서,하지만 난에서 D.에 526 00:22:08,802 --> 00:22:10,760 그래서이있을거야 이 나무에서 더 많은 노드. 527 00:22:10,760 --> 00:22:12,325 우리는 더 많은 통화의 malloc이 될 것입니다. 528 00:22:12,325 --> 00:22:14,700 하지만 난을 만들고 싶어하지 않는다 이 그림의 완전 엉망. 529 00:22:14,700 --> 00:22:17,710 그래서 대신 하나를 살펴 보자 그는 미리 책정 된 것 530 00:22:17,710 --> 00:22:21,810 점없는이 같은 점, 점,하지만 줄여서 배열. 531 00:22:21,810 --> 00:22:23,950 그러나 각 노드 여기이 나무 위로의 532 00:22:23,950 --> 00:22:26,700 같은 건 말인데 ...을 나타냅니다 배열 크기 (26)의 레이. 533 00:22:26,700 --> 00:22:28,860 >> 아니면 우리가 수 있도록하려면 정말 적절한 지금, 무엇을 534 00:22:28,860 --> 00:22:30,790 다른 사람의 이름과 같은 경우 아포스트로피는의를하자 535 00:22:30,790 --> 00:22:35,560 각 노드가 실제로 있다고 가정 그것은 27 인덱스, 단지 26 등을들 수있다. 536 00:22:35,560 --> 00:22:42,020 그래서 지금은 데이터가 될 것입니다 구조는 trie-- T-R-I-E라고합니다. 537 00:22:42,020 --> 00:22:46,120 아마 인 트라이, 나무에 대한 역사적 영리한 이름 538 00:22:46,120 --> 00:22:49,040 그은을 위해 최적화 된 검색, 이는 물론, 539 00:22:49,040 --> 00:22:50,870 이 트라이 그래서 I-E 철자된다. 540 00:22:50,870 --> 00:22:52,710 그러나 그것은 트라이의 역사입니다. 541 00:22:52,710 --> 00:22:55,860 >> 그래서 트라이이 나무와 같은 데이터는 가족 나무와 같은 구조 542 00:22:55,860 --> 00:22:57,510 즉 궁극적으로 그런 동작합니다. 543 00:22:57,510 --> 00:23:00,890 그리고 여기의 또 다른 예이다 다른 사람의 이름의 전체 무리. 544 00:23:00,890 --> 00:23:03,540 하지만 지금 질문 손에있는 것입니다 545 00:23:03,540 --> 00:23:08,070 우리는 틀림없이 더 도입하여 얻은 복잡한 데이터 구조, 및 한 546 00:23:08,070 --> 00:23:09,870 솔직히, 그 많은 메모리를 사용합니다. 547 00:23:09,870 --> 00:23:11,703 >> , 비록 때문에 순간, 난 단지 해요 548 00:23:11,703 --> 00:23:15,050 D의 포인터를 사용하여 V와 ES 및, NS 및 549 00:23:15,050 --> 00:23:16,700 나는 메모리 많아서을 낭비하고 있습니다. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 하지만 하나의 자원을 소비하는 경우, 난 다시 서로를 얻는가하는 경향이있다. 552 00:23:22,660 --> 00:23:26,020 나는 더 많은 공간을 소비하고있어 경우에 따라서 아마 희망이 무엇입니까? 553 00:23:26,020 --> 00:23:27,407 나는 무엇을 덜 지출이야? 554 00:23:27,407 --> 00:23:28,240 청중 : 적은 시간. 555 00:23:28,240 --> 00:23:28,990 DAVID 마란 : 시간. 556 00:23:28,990 --> 00:23:30,320 이제 그 이유가 될 수 있을까요? 557 00:23:30,320 --> 00:23:33,880 음, 삽입은 무엇인가 시간, 지금 큰 O의 관점에서, 558 00:23:33,880 --> 00:23:37,660 데 이븐 같은 이름의 또는 데븐 포트 또는 데이비드? 559 00:23:37,660 --> 00:23:39,340 음, 데 이븐은 다섯 단계이었다. 560 00:23:39,340 --> 00:23:42,350 데븐 포트는 아홉 단계가 될 것입니다, 그래서 몇 가지 단계가 될 것입니다. 561 00:23:42,350 --> 00:23:44,250 다윗은뿐만 아니라 다섯 단계가 될 것입니다. 562 00:23:44,250 --> 00:23:47,230 그래서 사람들은 콘크리트입니다 번호, 그러나 확실하게있다 563 00:23:47,230 --> 00:23:49,550 에 상한 다른 사람의 이름의 길이. 564 00:23:49,550 --> 00:23:52,240 그리고 사실,이 문제에 다섯 사양의 세트, 565 00:23:52,240 --> 00:23:54,050 우리가 제안하는거야 그것은 뭔가 그 566 00:23:54,050 --> 00:23:55,470 즉 40 일부-이상한 문자입니다. 567 00:23:55,470 --> 00:23:58,180 >> 현실적으로, 아무도 없습니다 무한히 긴 이름, 568 00:23:58,180 --> 00:24:01,542 말을하는 것입니다 것을의 길이 이름이나 문자열의 길이 우리는 수도 569 00:24:01,542 --> 00:24:03,750 국가의 특정이 구조는 틀림없이 무엇인가? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 그것은 상수입니다. 572 00:24:06,250 --> 00:24:06,430 오른쪽? 573 00:24:06,430 --> 00:24:09,310 이 같은 큰 상수 수 있습니다 40 일이 있지만, 일정하다. 574 00:24:09,310 --> 00:24:13,752 그리고 얼마나 많은에 대한 종속성이 없습니다 다른 이름은이 데이터 구조에 있습니다. 575 00:24:13,752 --> 00:24:15,460 즉, 만약 I 지금 삽입하고 싶어 576 00:24:15,460 --> 00:24:20,540 콜튼 또는 가브리엘 또는 롭 또는 Zamyla 또는 앨리슨 또는 벨린다 또는 다른 이름 577 00:24:20,540 --> 00:24:23,940 이 데이터로 직원 구조는 실행 시간 578 00:24:23,940 --> 00:24:26,750 다른 이름을 삽입 모든 영향에 될 것 579 00:24:26,750 --> 00:24:30,220 얼마나 많은 다른 요소가 있습니다 이미 데이터 구조? 580 00:24:30,220 --> 00:24:31,040 그것은 아니다. 581 00:24:31,040 --> 00:24:31,540 오른쪽? 582 00:24:31,540 --> 00:24:36,150 우리가 효율적으로 사용하기 때문에 이 다층 해시 테이블. 583 00:24:36,150 --> 00:24:38,280 그리고의 실행 시간 이러한 작업의 584 00:24:38,280 --> 00:24:41,510 의 수에 의존하지 않는 것입니다 데이터 구조적인 요소 585 00:24:41,510 --> 00:24:43,090 또는 결국 가고있다 데이터 구조하기 위해, 586 00:24:43,090 --> 00:24:44,714 하지만 구체적으로 어떤 길이에? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> 되는 문자열 삽입 만들 않는 589 00:24:49,200 --> 00:24:52,580 이 점근 일정 하나의 외엔 큰 O. 590 00:24:52,580 --> 00:24:54,720 그리고 솔직히, 그냥 실제,이 591 00:24:54,720 --> 00:24:58,380 데 이븐의 이름이 걸립니다 삽입 의미 다섯 단계, 또는 데이븐포트 - 9 592 00:24:58,380 --> 00:25:00,100 단계, 또는 데이비드 다섯 단계. 593 00:25:00,100 --> 00:25:03,071 즉 무척 작은 실행 시간입니다. 594 00:25:03,071 --> 00:25:05,320 그리고, 사실, 그건 매우있어 좋은 일이, 특히 595 00:25:05,320 --> 00:25:08,126 이 총에 의존 아니다 이 요소의 수. 596 00:25:08,126 --> 00:25:10,500 그래서 우리는 이것을 구현하는 방법 코드의 구조를 가지? 597 00:25:10,500 --> 00:25:12,900 그것은 좀 더있어 복잡한, 그러나 아직도이다 598 00:25:12,900 --> 00:25:15,050 단지 응용 프로그램 기본 빌딩 블록입니다. 599 00:25:15,050 --> 00:25:17,830 나는 다시 정의 할거야 우리 노드 다음과 같이 600 00:25:17,830 --> 00:25:21,100 부울 word--라는이를 아무것도라고 할 수있다. 601 00:25:21,100 --> 00:25:23,970 그러나 부울 나타냅니다 내가 체크 표시로 그렸습니다. 602 00:25:23,970 --> 00:25:24,490 예. 603 00:25:24,490 --> 00:25:26,720 이 문자열의 끝 이 데이터 구조. 604 00:25:26,720 --> 00:25:30,702 >> 그리고, 물론, 노드 별 아이들에게이 참조된다. 605 00:25:30,702 --> 00:25:32,410 그리고, 참으로, 단지 좋아 가계도, 당신 606 00:25:32,410 --> 00:25:34,370 노드를 고려할 것 이 걸려있다 607 00:25:34,370 --> 00:25:36,920 일부 부모의 아래쪽의 요소는 아이들합니다. 608 00:25:36,920 --> 00:25:40,510 그래서 아이들이 가고있다 (27)의 배열, 27 일 하나 609 00:25:40,510 --> 00:25:41,680 단지 아포​​스트로피하기위한 것이다. 610 00:25:41,680 --> 00:25:43,390 우리는 정렬 할거야 특별한 경우 그. 611 00:25:43,390 --> 00:25:45,400 그래서 당신은 어떤을 가질 수 있습니다 아포스트로피 이름. 612 00:25:45,400 --> 00:25:47,399 어쩌면 하이픈해야 거기에 가서,하지만 당신은거야 613 00:25:47,399 --> 00:25:50,330 P 세트 (5) 우리는주의에서 볼 문자와 아포스트로피에 대한. 614 00:25:50,330 --> 00:25:52,990 >> 그리고 당신은 어떻게 표현 할 데이터 구조 자체? 615 00:25:52,990 --> 00:25:56,454 어떻게 루트를 표시합니까 이 트라이의, 말하자면? 616 00:25:56,454 --> 00:25:59,620 글쎄, 당신은, 연결리스트와 같은 첫 번째 요소에 대한 포인터가 필요합니다. 617 00:25:59,620 --> 00:26:04,270 트라이하면 하나의 필요 이 트라이의 루트 포인터. 618 00:26:04,270 --> 00:26:07,290 그리고 거기에서 당신은 해시 수 있습니다 길 아래로 점점 더 깊이 619 00:26:07,290 --> 00:26:10,460 구조에서 다른 모든 노드. 620 00:26:10,460 --> 00:26:13,440 그래서 단순히이 수와 우리는 그 구조체를 나타냅니다. 621 00:26:13,440 --> 00:26:15,877 >> 이제, 오 질문을 Meanwhile--. 622 00:26:15,877 --> 00:26:17,220 >> 청중 : 부울 단어가 무엇입니까? 623 00:26:17,220 --> 00:26:20,490 >> DAVID 마란은 Bool로 단어입니다 그냥이 C 화신 624 00:26:20,490 --> 00:26:22,920 제가 설명 무엇을 여기에, 때이 상자에 625 00:26:22,920 --> 00:26:26,000 I는 각 분할 시작한 두 조각으로 배열의 요소. 626 00:26:26,000 --> 00:26:27,600 하나는 다음 노드에 대한 포인터이다. 627 00:26:27,600 --> 00:26:30,280 다른 하나는 있어야한다 체크 박스 같은 628 00:26:30,280 --> 00:26:33,770 거기에 '좋아요'라고 말하고 여기서 끝 데 이븐 단어, 629 00:26:33,770 --> 00:26:35,610 우리가 원하는하지 않기 때문에 순간, 데이브. 630 00:26:35,610 --> 00:26:39,320 >> 데이브을 될 것입니다 비록 합법적 인 단어, 그는 트라이에없는 631 00:26:39,320 --> 00:26:39,830 아직. 632 00:26:39,830 --> 00:26:40,950 그리고 D는 단어가 아닙니다. 633 00:26:40,950 --> 00:26:42,770 그리고 D-A는 단어 나 이름이 아닙니다. 634 00:26:42,770 --> 00:26:45,020 체크 표시 그래서 만 번을 나타냅니다 635 00:26:45,020 --> 00:26:48,190 이 노드 인 히트 문자의 이전 경로 636 00:26:48,190 --> 00:26:50,700 당신이 삽입 한 사실 문자열입니다. 637 00:26:50,700 --> 00:26:53,660 그래서 모든 부울이다 우리가하고있다. 638 00:26:53,660 --> 00:26:55,500 >> 시도에 다른 질문? 639 00:26:55,500 --> 00:26:56,215 그래. 640 00:26:56,215 --> 00:26:58,035 >> 청중 : 중첩은 무엇입니까? 641 00:26:58,035 --> 00:26:59,945 당신이 데이브와 데 이븐이 있다면? 642 00:26:59,945 --> 00:27:00,820 DAVID 마란 : 완벽한. 643 00:27:00,820 --> 00:27:02,580 당신이 데이브와 데 이븐이 있다면? 644 00:27:02,580 --> 00:27:06,240 우리가 삽입한다면, 별명 말 의원님 Dave-- D-A-V-E 하시나요? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 이것은 실제로 매우 간단합니다. 647 00:27:08,700 --> 00:27:10,325 그래서 우리는 네 가지 조치를 취할 것입니다. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. 그리고 난에 무엇을해야합니까 내가 그 제 4 노드에 충돌하면 어떻게? 650 00:27:15,847 --> 00:27:16,680 그냥 확인하는 것. 651 00:27:16,680 --> 00:27:18,000 우리는 이미 갈 수 있어요. 652 00:27:18,000 --> 00:27:18,840 완료. 653 00:27:18,840 --> 00:27:19,750 네 단계. 654 00:27:19,750 --> 00:27:21,590 점근 적으로 일정 시간. 655 00:27:21,590 --> 00:27:26,300 그리고 지금 우리는 모두 데이브 표시했습니다 그리고 데 이븐은 구조 문자열입니다. 656 00:27:26,300 --> 00:27:27,710 그래서 문제가되지 않는다. 657 00:27:27,710 --> 00:27:30,200 그리고 어떻게 존재를 알 데 이븐의 그것을하지 않았다 658 00:27:30,200 --> 00:27:34,750 더 이상 시간 미만을 시간 데이브 및 그 반대의 경우도 마찬가지입니다. 659 00:27:34,750 --> 00:27:36,000 >> 그래서 우리는 지금 다른 무엇을 할 수 있습니까? 660 00:27:36,000 --> 00:27:40,680 우리는 전에이 은유를 사용했습니다 트레이의 무언가를 나타내는. 661 00:27:40,680 --> 00:27:43,380 그러나 그것은 밝혀 트레이의 스택은 실제로 662 00:27:43,380 --> 00:27:47,187 다른 추상 데이터의 실증 높은 레벨의 데이터 구조 유형 선택 663 00:27:47,187 --> 00:27:49,770 마지막에 날 그냥입니다 배열이나 연결리스트 같은 664 00:27:49,770 --> 00:27:50,970 현세 또는 뭔가. 665 00:27:50,970 --> 00:27:53,270 그러나 더 흥미있어 개념, 개념. 666 00:27:53,270 --> 00:27:56,440 이와 같은 스택, 메이 여기에 트레이, 667 00:27:56,440 --> 00:27:58,750 일반적으로 호출 다만 스택을 ... 그 얘기. 668 00:27:58,750 --> 00:28:02,540 >> 그리고, 데이터 구조의이 유형의 두 operations--이 669 00:28:02,540 --> 00:28:05,880 당신은 하나라는 푸시에 대한이 스택에 뭔가를 추가, 670 00:28:05,880 --> 00:28:08,320 다른 용지함을 씌우고 스택의 상단에 백업합니다. 671 00:28:08,320 --> 00:28:11,350 당신을 의미하는 그리고 팝 맨 위의 트레이 이륙. 672 00:28:11,350 --> 00:28:16,210 그러나 스택이 있다는 것입니다에 대한 주요 무엇 그것은이 호기심 특성을 가지고있다. 673 00:28:16,210 --> 00:28:19,560 식당 직원과 같습니다 다음 식사 트레이를 정리, 674 00:28:19,560 --> 00:28:21,380 무슨 일이있을거야 어떻게 학생들에 대한 진실 675 00:28:21,380 --> 00:28:22,856 데이터 구조와 상호 작용? 676 00:28:22,856 --> 00:28:24,480 청중 : 그들은 하나 오프 팝업 것입니다. 677 00:28:24,480 --> 00:28:26,550 DAVID 마란 : 그들은 갈거야 하나 떨어져, 희망 상단 팝업. 678 00:28:26,550 --> 00:28:28,910 그렇지 않으면 그것은 단지 종류의 바보 바닥에 모든 방법을 이동합니다. 679 00:28:28,910 --> 00:28:29,070 오른쪽? 680 00:28:29,070 --> 00:28:31,620 데이터 구조는 실제로 허용하지 않는다 적어도 하단 트레이를 잡아합니다 681 00:28:31,620 --> 00:28:32,520 쉽게. 682 00:28:32,520 --> 00:28:35,040 그래서이 호기심있다 스택에 등록 683 00:28:35,040 --> 00:28:39,730 마지막 항목은 그 첫 번째 아웃 될 것이다. 684 00:28:39,730 --> 00:28:43,400 그리고 컴퓨터 과학자들은 전화 이 먼저 아웃 지속 LIFO--. 685 00:28:43,400 --> 00:28:45,540 그리고 실제 존재하는 흥미로운 응용 프로그램. 686 00:28:45,540 --> 00:28:50,090 그것은 반드시 어떤만큼 명백하지 않다면, 다른하지만​​, 실제로, 유용 687 00:28:50,090 --> 00:28:54,040 그리고, 실제로 구현 될 수있다 다른 몇 가지 방법. 688 00:28:54,040 --> 00:28:58,550 >> 그래서 하나, 실제로,하자 나는에 뛰어하지. 689 00:28:58,550 --> 00:28:59,860 의 대신이 작업을 수행 할 수 있습니다. 690 00:28:59,860 --> 00:29:03,700 의 거의이야, 하나 살펴 보자 동일한 아이디어는 있지만 좀 더 공정이다. 691 00:29:03,700 --> 00:29:04,200 오른쪽? 692 00:29:04,200 --> 00:29:07,560 이러한 팬 소년의 하나라면 또는 정말 애플 제품을 좋아하는 여자 693 00:29:07,560 --> 00:29:10,130 당신은 오전 3시 일어났다 일부 가게에서 줄을 694 00:29:10,130 --> 00:29:14,150 최신 아이폰을 얻으려면, 이처럼 대기했을 수 있습니다. 695 00:29:14,150 --> 00:29:15,800 >> 이제 큐는 매우 의도적으로 지정됩니다. 696 00:29:15,800 --> 00:29:18,190 이 때문에이 라인의 그것은 몇 가지 공정성. 697 00:29:18,190 --> 00:29:18,690 오른쪽? 698 00:29:18,690 --> 00:29:21,690 만약 여러분의 경우는 가지 빨려 것 애플 스토어에 처음 도착했을 699 00:29:21,690 --> 00:29:25,700 하지만 당신은 효과적으로 맨 아래에 있습니다 트레이 후 애플 직원 때문에 700 00:29:25,700 --> 00:29:28,189 마지막 사람을 팝업 사람 실제로 라인에있어. 701 00:29:28,189 --> 00:29:31,230 스택과 큐, 비록 그래서 기능적으로 그들은 same-- 가지있어 702 00:29:31,230 --> 00:29:33,105 그냥이 컬렉션의 자원 그건 703 00:29:33,105 --> 00:29:36,210 이 것 shrink-- 성장에 가서 그것은이 공정성 측면, 704 00:29:36,210 --> 00:29:39,634 현실 세계에서 적어도, 여기서 작업은 당신이 운동 705 00:29:39,634 --> 00:29:40,800 근본적으로 다르​​다. 706 00:29:40,800 --> 00:29:43,360 큐 stack-- rather-- 가지고 있다고 707 00:29:43,360 --> 00:29:45,320 두 가지 작업 : N 큐와 D 큐. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 또는 당신이 그들을 호출 할 수 있습니다 일의 수. 710 00:29:48,090 --> 00:29:50,770 그러나 당신은 캡처 할 하나를 추가한다는 개념 711 00:29:50,770 --> 00:29:53,230 하나는 궁극적으로 차감됩니다. 712 00:29:53,230 --> 00:29:58,840 >> 지금은 후드 아래, 두 스택 그리고 큐는 어떻게 구현 될 수 있을까? 713 00:29:58,840 --> 00:30:01,390 우리의 코드로 가지 않을 것이다 그 때문에 높은 레벨 714 00:30:01,390 --> 00:30:03,387 아이디어는 일종의 더 분명하다. 715 00:30:03,387 --> 00:30:04,470 내 말은, 인간은 무엇을해야합니까? 716 00:30:04,470 --> 00:30:07,030 나는 애플의 첫 번째 사람이야 경우 저장하고이 정문이다, 717 00:30:07,030 --> 00:30:08,130 내가 여기 서거야, 알아. 718 00:30:08,130 --> 00:30:09,750 그리고 다음 사람의 여기 서서 것. 719 00:30:09,750 --> 00:30:11,500 그리고 다음 사람의 여기 서서 것. 720 00:30:11,500 --> 00:30:13,792 그래서 데이터 구조 그 자체가 큐에 빌려 준다? 721 00:30:13,792 --> 00:30:14,542 >> 청중 : 큐. 722 00:30:14,542 --> 00:30:15,667 DAVID 마란 : 음, 큐. 723 00:30:15,667 --> 00:30:16,390 물론. 724 00:30:16,390 --> 00:30:16,920 그 밖의 무엇? 725 00:30:16,920 --> 00:30:17,600 >> 청중 : 연결리스트. 726 00:30:17,600 --> 00:30:18,990 >> DAVID 마란 : 링크 당신이 구현할 수있는 목록입니다. 727 00:30:18,990 --> 00:30:22,500 그리고 연결리스트는 때문에 좋은 반대로 그것은 긴 임의 성장할 수 728 00:30:22,500 --> 00:30:24,880 어떤 고정 된 수를 갖는 것 상점에있는 사람들의. 729 00:30:24,880 --> 00:30:27,030 하지만 어쩌면 고정 된 수의 장소의 합법적이다. 730 00:30:27,030 --> 00:30:30,350 그들은 20처럼이있는 경우 때문에 어쩌면, 첫날 아이폰 731 00:30:30,350 --> 00:30:33,930 그들은 단지 크기의 어레이를 필요 (20)는 그 큐를 대표 할 732 00:30:33,930 --> 00:30:37,070 우리가 이야기를 시작하면 지금은 말을하는 것입니다 이러한 높은 수준의 문제에 대한, 733 00:30:37,070 --> 00:30:38,890 당신은 그것을 구현할 수 있습니다 임의의 수의 방법. 734 00:30:38,890 --> 00:30:42,030 그리고 아마 가고있다 공간과 시간에서 무역을 할 수 735 00:30:42,030 --> 00:30:43,950 또는 당신의 자신의 코드 복잡성. 736 00:30:43,950 --> 00:30:45,380 >> 스택은 어떻습니까? 737 00:30:45,380 --> 00:30:48,190 음, 스택, 우리는 너무 본 적이 다만이 트레이 수 있습니다. 738 00:30:48,190 --> 00:30:50,007 그리고 당신은이 배열을 구현할 수 있습니다. 739 00:30:50,007 --> 00:30:53,090 그러나 어떤 시점에서 당신은 배열을 사용하는 경우 무엇 트레이에 일어날 740 00:30:53,090 --> 00:30:54,173 당신은 내려 놓으려고? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 좋아. 743 00:30:55,670 --> 00:30:57,490 당신은에 갈거야 그래서 높은 갈 수. 744 00:30:57,490 --> 00:31:00,156 그리고 나는 그들이있어 메이 생각 실제로 개방에 함몰. 745 00:31:00,156 --> 00:31:01,950 그래서 실제로, 거의이다 메이가 사용하는 같은 746 00:31:01,950 --> 00:31:03,783 고정 크기의 배열 만 할 수 있기 때문에 747 00:31:03,783 --> 00:31:08,302 에서 그 열기에 너무 많은 트레이에 맞게 사람의 무릎 아래 아래로 벽. 748 00:31:08,302 --> 00:31:10,010 그리고 그 수 있습니다 배열이라고, 749 00:31:10,010 --> 00:31:14,300 그러나 우리는 확실히 구현할 수 더 일반적으로 링크 된 목록. 750 00:31:14,300 --> 00:31:16,390 >> 그럼, 다른 데이터 구조에 대한? 751 00:31:16,390 --> 00:31:18,760 내가 여기에 시각적 다른 하나를 올려 보자. 752 00:31:18,760 --> 00:31:24,710 어떻게 여기 하나에 대해 같은 뭔가? 753 00:31:24,710 --> 00:31:28,920 왜하지 않은 것이 유용 할 수도 있습니다 트라이만큼 멋진 뭔가하는 754 00:31:28,920 --> 00:31:32,370 우리는 이러한 매우 넓은 노드보고 ... 이들은 각각 배열인가? 755 00:31:32,370 --> 00:31:35,740 그러나 우리는 뭔가 더 많은 일을 할 경우 단순히 오래된 학교 가족 나무처럼, 756 00:31:35,740 --> 00:31:38,110 누구 여기에 각 노드 단지 수를 저장한다. 757 00:31:38,110 --> 00:31:42,180 대신 이름 또는 자손의 다만이 같은 번호를 저장한다. 758 00:31:42,180 --> 00:31:45,250 >> 음, 전문 용어는 우리가에 사용 데이터 구조는 모두 시도이고 759 00:31:45,250 --> 00:31:49,510 나무, 트라이는 다시, 어디 단지 그 노드 배열은 하나, 760 00:31:49,510 --> 00:31:51,680 아직도 당신은 무엇을 수도 초등학교에서 사용 761 00:31:51,680 --> 00:31:53,860 당신은 가족을 만들 때 tree-- 잎과 뿌리 762 00:31:53,860 --> 00:31:57,250 나무와 아이들의 부모와 그 형제 자매. 763 00:31:57,250 --> 00:32:03,670 그리고 우리는 나무를 구현할 수, 예를 들어, 단순히이있다. 764 00:32:03,670 --> 00:32:07,420 나무, 그 경우 노드의 하나로서 번호가 이러한 원, 765 00:32:07,420 --> 00:32:09,947 그것은이 없을거야 하나의 포인터 만 두. 766 00:32:09,947 --> 00:32:11,780 그리고 곧 추가로 두 번째 포인터, 당신 767 00:32:11,780 --> 00:32:13,905 실제로 정렬 할 수 있습니다 이차원 데이터 768 00:32:13,905 --> 00:32:14,780 메모리의 구조. 769 00:32:14,780 --> 00:32:16,660 두 차원과 마찬가지로 배열, 당신은 할 수 770 00:32:16,660 --> 00:32:18,904 두 차원의 종류가 연결리스트하지만 사람 771 00:32:18,904 --> 00:32:20,820 그 패턴을 따라 위치에 상관주기를가 없습니다. 772 00:32:20,820 --> 00:32:24,487 그것은 하나의 진정으로 나무의 여기에 다음 조부모 길 773 00:32:24,487 --> 00:32:27,320 일부 부모와 자녀와 손자와 증손자. 774 00:32:27,320 --> 00:32:28,370 등. 775 00:32:28,370 --> 00:32:32,390 >> 그러나, 너무이 정말 깔끔한 무엇 단지 코드의 비트와 함께 당신을 괴롭혀, 776 00:32:32,390 --> 00:32:35,370 에서 리콜 재귀 잠시 뒤로, 이에 777 00:32:35,370 --> 00:32:38,220 당신은 자신을 호출하는 함수를 작성합니다. 778 00:32:38,220 --> 00:32:41,140 이 아름다운 기회 어떤 구현 779 00:32:41,140 --> 00:32:42,920 재귀처럼, 때문에이를 고려한다. 780 00:32:42,920 --> 00:32:43,860 >> 이 나무입니다. 781 00:32:43,860 --> 00:32:48,040 그리고 방법에 약간의 항문 봤는데 나는 거리에 정수를 넣어. 782 00:32:48,040 --> 00:32:51,020 그래야 많이 특수가 이진 검색 트리를 이름 -. 783 00:32:51,020 --> 00:32:53,460 이제 우리는 바이너리 들었어요 당신을 검색 할 수 있지만, 784 00:32:53,460 --> 00:32:55,180 이 물건의 이름에서 거꾸로? 785 00:32:55,180 --> 00:32:59,280 나는 방법의 패턴은 무엇입니까 이 나무에 정수를 삽입? 786 00:32:59,280 --> 00:33:00,696 그것은 임의 아니다. 787 00:33:00,696 --> 00:33:01,570 몇 가지 패턴이있다. 788 00:33:01,570 --> 00:33:02,090 그래. 789 00:33:02,090 --> 00:33:03,370 >> 청중 : 왼쪽에있는 작은 것들. 790 00:33:03,370 --> 00:33:03,690 >> DAVID 마란 : 그래. 791 00:33:03,690 --> 00:33:05,062 작은 사람은 왼쪽에 있습니다. 792 00:33:05,062 --> 00:33:06,270 더 큰 사람은 오른쪽에 있습니다. 793 00:33:06,270 --> 00:33:12,940 이러한 사실 문이있는 부모, 좌측 자식보다 큰 794 00:33:12,940 --> 00:33:14,850 오른쪽 아이보다 미만. 795 00:33:14,850 --> 00:33:17,750 그리고 혼자 심지어입니다 재귀 언어 적 정의 796 00:33:17,750 --> 00:33:20,500 당신은 적용 할 수 있기 때문에 모든 노드에 같은 논리 797 00:33:20,500 --> 00:33:23,080 그리고 단지 바닥 아웃, 기본 케이스 괜찮다면 798 00:33:23,080 --> 00:33:25,740 의지 할 때 중 하나를 명중 잎은, 그래서, 말하자면 799 00:33:25,740 --> 00:33:28,580 휴가는 더 아이가없는 곳. 800 00:33:28,580 --> 00:33:30,614 >> 이제 당신은 어떻게 수 (44)를 찾을 수 있습니까? 801 00:33:30,614 --> 00:33:32,280 당신은, 흠 루트에 시작하고 말할 것입니다. 802 00:33:32,280 --> 00:33:35,690 55 그래서 내가 가고 싶어 (44) 아니다 오른쪽 또는 내가 왼쪽으로 가고 싶어? 803 00:33:35,690 --> 00:33:37,190 글쎄, 확실히 당신은 왼쪽으로 가고 싶어. 804 00:33:37,190 --> 00:33:40,060 그래서 그냥 전화처럼 이진 검색에서 책의 예 805 00:33:40,060 --> 00:33:41,099 더 일반적으로. 806 00:33:41,099 --> 00:33:43,390 그러나 우리는 그것을 구현하고 이제 좀 더 동적 807 00:33:43,390 --> 00:33:45,339 어레이가 허용 할 수보다도. 808 00:33:45,339 --> 00:33:48,130 그리고 사실, 당신이보고 싶은 경우 코드에서 먼저 눈에 확인합니다. 809 00:33:48,130 --> 00:33:49,671 이 라인의 전체 무리처럼 보인다. 810 00:33:49,671 --> 00:33:51,220 그러나 그것은 아름답게 간단합니다. 811 00:33:51,220 --> 00:33:54,490 당신은 기능을 구현하려면 그 목적은 인생에서라는 검색 812 00:33:54,490 --> 00:33:57,290 값을 검색하는 것입니다 같은 n은 정수, 813 00:33:57,290 --> 00:34:01,756 당신은 하나 pointer--에 전달하고 뿌리의 노드에 대한 포인터, 814 00:34:01,756 --> 00:34:04,380 오히려, 그 나무의 어떤에서 당신은, 다른 모든 것들에 액세스 할 수 있습니다 815 00:34:04,380 --> 00:34:08,850 어떻게 똑 바르게 알 당신은 논리를 구현할 수 있습니다. 816 00:34:08,850 --> 00:34:10,880 나무가 null의 경우는, 분명히이 아니다. 817 00:34:10,880 --> 00:34:11,880 그냥 false를 돌려 보자. 818 00:34:11,880 --> 00:34:12,000 오른쪽? 819 00:34:12,000 --> 00:34:14,040 당신은 그에게 아무 것도 손없는 경우, 거기에 아무것도 없다. 820 00:34:14,040 --> 00:34:17,900 >> n은 그렇지 미만이면 지금 N 화살표 N-- 나무 화살표, 821 00:34:17,900 --> 00:34:20,670 우리가 슈퍼를 도입 리콜 잠시 다른 일, 822 00:34:20,670 --> 00:34:25,100 그것은 바로 드 참조를 의미 포인터와 N이라는 필드를 확인합니다. 823 00:34:25,100 --> 00:34:27,690 그래서 가서 의미 N이라는 필드를 확인합니다. 824 00:34:27,690 --> 00:34:33,810 그래서 N 경우, 당신이 제공하고있는 값이 작 나무의 정수 값보다, 825 00:34:33,810 --> 00:34:35,449 어디 가고 싶어? 826 00:34:35,449 --> 00:34:36,389 왼쪽으로. 827 00:34:36,389 --> 00:34:37,780 >> 그래서 재귀를 알 수 있습니다. 828 00:34:37,780 --> 00:34:39,860 난 안 사실 returning--하고 있습니다. 829 00:34:39,860 --> 00:34:40,989 거짓되지 않습니다. 830 00:34:40,989 --> 00:34:45,670 내가 어떤 대답을 반환 해요 자신에 대한 호출에서이다, 통과 831 00:34:45,670 --> 00:34:50,100 중복 다시 N, 하지만 지금은 약간의 차이는 무엇입니까? 832 00:34:50,100 --> 00:34:51,989 어떻게 작은 문제를하고 있죠? 833 00:34:51,989 --> 00:34:54,920 나는 두 번째로 통과 해요 인수, 트리의 루트가 아닌, 834 00:34:54,920 --> 00:34:59,616 그러나이 경우에는 좌측 아이. 835 00:34:59,616 --> 00:35:00,990 그래서 왼쪽 자식을 전달하고 있습니다. 836 00:35:00,990 --> 00:35:04,720 >> 한편, n은보다 큰이면 나는 현재 찾고 있어요 노드, 837 00:35:04,720 --> 00:35:06,690 나는 오른쪽을 검색 할 수 있습니다. 838 00:35:06,690 --> 00:35:10,880 그렇지, 나무, null가 아닌 경우 요소는 왼쪽이 아니라면 839 00:35:10,880 --> 00:35:13,240 그리고, 오른쪽 아니다 경우 멋지고 무엇인가? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 우리는 실제로에서 노드를 발견했습니다 질문은, 그래서 우리는 true를 돌려줍니다. 842 00:35:18,440 --> 00:35:21,490 >> 그래서 우리는 단지 표면을 다루었 이제 이러한 데이터 구조의 일부. 843 00:35:21,490 --> 00:35:24,370 문제는 다섯 설정에서 당신은거야 또 다른이를 탐험, 844 00:35:24,370 --> 00:35:27,250 당신은 당신의 디자인이 제공됩니다 이것에 대해 이동하는 방법을 선택. 845 00:35:27,250 --> 00:35:30,250 나는에 체결하고 싶습니다 무엇 단지 30 초 티저입니다 846 00:35:30,250 --> 00:35:32,080 넘어 다음 주에 기다리고 무엇. 847 00:35:32,080 --> 00:35:35,390 >> 우리는 다행히 begin--로서 당신은 수도 천천히 우리의 전환을 생각 엔 ... 848 00:35:35,390 --> 00:35:38,680 C와 하부의 세계에서 레벨 구현 세부 사항 849 00:35:38,680 --> 00:35:42,090 세계에있는 우리가 걸릴 수 있습니다 다른 사람이 마지막으로 가지고 부여 850 00:35:42,090 --> 00:35:44,010 이러한 데이터를 구현 우리를 위해 구조, 851 00:35:44,010 --> 00:35:47,570 그리고 우리는을 이해하기 시작합니다 현실 세계가 구현 수단 852 00:35:47,570 --> 00:35:50,560 웹 기반 프로그램과 웹 사이트보다 일반적으로 853 00:35:50,560 --> 00:35:52,910 또한 매우 보안 우리 만했습니다 의미 854 00:35:52,910 --> 00:35:54,850 의 표면에 흠집을하기 시작. 855 00:35:54,850 --> 00:35:57,320 여기에서 우리를 기다리고 무엇인가 시대에 와서. 856 00:35:57,320 --> 00:36:00,480 >> [동영상 재생] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> - 그는, 메시지와 함께 모든 자신의 프로토콜. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 그는 잔인의 세계에 온 방화벽, 무관 심한 라우터, 861 00:36:30,894 --> 00:36:33,368 및 위험 죽음보다 훨씬 더. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 그는 빠르다. 864 00:36:36,236 --> 00:36:37,980 그는 강한. 865 00:36:37,980 --> 00:36:42,830 그는 TCP / IP, 그리고 그는 당신의 주소를 가지고있다. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "인터넷의 전사." 868 00:36:48,074 --> 00:36:49,660 [END 동영상 재생] 869 00:36:49,660 --> 00:36:50,910 DAVID 마란 : 다음 주에 간다. 870 00:36:50,910 --> 00:36:51,880 우리는 당신이 다음 볼 수 있습니다. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [동영상 재생] 873 00:36:56,060 --> 00:36:59,240 - 그리고 지금, "깊은 생각" 데 이븐 판햄로. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 데이비드는 항상 시작 와 강의 "좋아요." 876 00:37:05,820 --> 00:37:08,750 왜, "여기에 솔루션입니다 이번 주 문제 세트 "에 877 00:37:08,750 --> 00:37:12,180 또는 "우리는 여러분 모두를주는거야?" 878 00:37:12,180 --> 00:37:13,380 [하하] 879 00:37:13,380 --> 00:37:15,530 [END 동영상 재생]