SNOW logo
  • 로그인 회원가입 도움말 ENGLISH
알고리즘 분석 (Analysis of Algorithms)
[정규강의] 알고리즘 입문 (Introduction to Algorithms) 1강/총23강
자막보기 자막감추기
메일보내기
트위터로 보내기
페이스북으로 보내기
북마크
소스복사
강의정보한글스크립트원문스크립트자막

강의소개  강의 전문보기

알고리즘에 대해 전반적으로 학습한다. 알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 설계하려는 알고리즘이 "무엇을"하는지를 입력과 출력에 의해 명시할 수 있다. 본 강의에서는 알고리즘 분석에 기초가 되는 수행시간, 표기법 등을 학습한다.

* MIT OCW 강의들은 SNOW에 의해서 번역되고 있습니다. MIT대학, MIT대학의 교수진들 및 MIT OCW는 SNOW가 번역한 스크립트를 검토하거나 승인하는 일과는 관계가 없습니다. MIT대학 및 MIT OCW는 SNOW의 번역물에 관련한 보증은 없으며, 상품성에 대한 보증과 특수한 목적, 사용 또는 적용을 위한 적합성 보증 및 모든 다른 의무와 책임을 포함하되 그에 제한되지 않고, 모든 다른 명시적 또는 묵시적 보증을 대체하고 배제합니다. MIT OCW는 번역 오류에 대해 어떠한 책임도 없으며 번역의 부정확함에 따른 어떠한 오류나 결함은 전적으로 MIT OCW가 아닌 SNOW에게 책임이 있다는 것을 명시하는 바입니다. (These MIT OpenCourseWare course materials have been translated into Korean by SNOW. The MIT faculty authors, MIT, or MIT OpenCourseWare have not reviewed or approved these translations, and MIT and MIT OpenCourseWare makes no representations or warranties of any kind concerning the translated materials, express or implied, including, without limitation, warranties of merchantability, fitness for a particular purpose, non-infringement, or the absence of errors, whether or not discoverable. MIT OpenCourseWare bears no responsibility for any inaccuracies in translation. Any inaccuracies or other defects contained in this material, due to inaccuracies in language translation, are the sole responsibility of SNOW and not MIT OpenCourseWare.)
님이 한글스크립트를 등록 해 주셨습니다.

동영상을 보기 위해 필요한 기본 전공 지식
■ 대분류: 알고리즘
■ 중분류: 알고리즘 이해
■ 소분류: 알고리즘 기초

동영상에서 중점적으로 봐야 할 부분
● 알고리즘 이해
● 수행시간, 표기법

참고서적
문병로(2007), 쉽게 배우는 알고리즘, 한빛미디어
박정호 외 3명(2011), C언어로 작성하는 컴퓨터 알고리즘, 이한출판사

관련 동영상
<관련 사이트>
프로그래밍 관련 자료 사이트
MIT 알고리즘 입문 course 사이트
펼쳐보기

작성참여하기  히스토리

프린트

*  
님이 등록 해 주셨습니다.
Lecture01. 알고리즘 분석 (Analysis of Algorithms) 
 
 
이제 수업 시작하겠습니다. 핸드아웃 가져가지 않은 학생은 문 옆에 있으니 가져가세요. 제이름은 찰스 라이저슨입니다. 이번학기에 에릭 데메인과 함께 알고리듬 입문 과목을 강의할 겁니다. 덧붙여 이건 데이비드 수에 의해 싱가포르에서 진행되고 있는 싱가포르 MIT 과정, SMA입니다. 그리고 모든 수업은 비디오 테이프로 녹화되고 웹을 통해 강의를 보기를 선택한 MIT 학생들 뿐만 아니라 웹을 통해 싱가폴 학생들이 볼 수 있도록 만들어 질 것입니다. 만약에 비디오에 녹화되지 않길 원하는 학생은 뒷줄에 앉아주시길 바랍니다. 됐나요? 그렇지 않으면 비디오 테잎에 녹화 될 것입니다. 비디오 녹화 정책이 있는데 만기된 것 같군요.  
 
만약 보고 싶으면 돌려가며 봐도 되고, 아니면 저한테 와도 됩니다. 제게 복사본이 하나 있습니다. 본격적으로 수업으로 들어가기 전에 간단하게 수업에 대한 정보를 살펴보도록 하겠습니다. 여러분이 보다시피 이번 학기에는 조교들이 아주 많습니다. 여기 핸드아웃을 보세요. 6명의 조교들을 포함해서 다른 학기 때보다 2명 더 많은 조교들이 있습니다. 그것은 특히 설명은 많지 않을 것이라는 것을 뜻하죠. 여기 웹 페이지가 있습니다. 모든 공지들이 이곳으로 올라오니 즐겨찾기 해두고 정기적으로 확인하기 바랍니다. 이메일. 여러분께 우리 이메일 주소를 알려 드려도 조교나 교수에게 직접 이메일을 보내지는 마시기 바랍니다. 이것은 여러분이 좀 더 빠른 답변을 받기 위한 것입니다. 
 
제가 이미 언급 했듯이, 이번 학기에 우리는 원격 교육을 하게 될 것이고, 그래서 인터넷으로 강의를 듣고 싶다면 여러분은 온라인으로 강의를 들을 수 있습니다. 볼 수 있는 기회를 가진 분들은 보는 것을 추천합니다. 그렇지만, 강의에 올 수 있는 분들은 아무래도 현장에 와서 강의를 듣는 것이 좋겠지요. 소통할 수 있고, 뭐라고 꼭 집어서 말할 수 없는 무언가가 있습니다. 사실 비디오 외에도 저는 싱가폴 학생들 또한 직접 들을 수 있도록 매주 모임을 가지고 있습니다. 필수요건. 이번 강의를 듣기 위해서 미리 알고 있어야 할 것은 컴퓨터 과학을 위한 수학, 6.042와 6.001입니다. 여러분이 이 과목을 잘 따라가기 위해서는 프로그래밍 경험 뿐만 아니라 기본적으로 이산수학과 확률에 대한 지식이 필요합니다. 이 선수 과목들을 수강하지 않은 분들은 이 수업을 들어서는 안 됩니다. 선수과목을 한번 체크해보도록 하지요. 질문이 있다면 수업이 끝난 후에 이야기 하도록 합시다. 
 
강의는 여기서 이루어지고, SMA 학생들은 비디오 테잎을 보고 매주 모임을 가질 것입니다. 학생들은 반드시 매주 있는 한 시간짜리 설명 시간에 출석 해야 합니다. 설명시간에 새로운 자료가 주어질 것이고, 이 수업과는 다르게 온라인으로는 제공되지 않을 것입니다. 또한 이 수업과 다르게 일반적으로 설명에 대해 주는 강의노트도 없을 것입니다. 그러나 그 시간에 직접적으로 시험에 관련된 자료가 나갈 것입니다. 그리고 매 학기 그랬던 것처럼 여러분이 배우고서 금세 까먹는 것을 잘 알기 때문에 여러분께 설명시간에 이 부분을 언제 다뤘었지? 라고 물어서 중요한 부분을 상기시켜 줄 것입니다.  
 
그래서 설명시간은 의무적으로 반드시 출석해야 합니다. 그리고 특히 설명시간 강사님도 여러분께 성적을 주는 사람들 중 하나라고 말씀 드리고 싶습니다. 우리는 성적 미팅을 가질 것이고, 설명시간은 여러분의 성적에 아주 큰 영향을 미칠 것입니다.  
 
핸드아웃들. 핸드아웃은 강좌 웹 페이지에서 볼 수 있고, 이번에 첫 번째 핸드아웃만 나눠드리고, 일반적으로 앞으로 나눠드릴 핸드아웃은 수업에 들고 들어오지는 않을 것입니다. 교재는 이 책입니다. Introduction to Algorithms. MIT 학생들은 MIT Coop을 포함해서 지역의 어느 서점에서도 이 책을 살 수 있습니다. 또한 교재를 파는 새로운 온라인 서비스가 있고, MIT Press 서점에서 사면 할인도 받을 수 있습니다. MIT Press 서점에서 할인 받을 수 있는 쿠폰이 MIT 전화번호부에 한 개 있습니다. 이 책을 구입하는데 할인을 사용할 수 있죠.  
 
강의 웹사이트. 이것이 강의 웹사이트입니다. 이것은 Stellar 사이트와 연결되는데, Stellar 사이트에 모든 것이 보관될 것입니다. 그리고 SMA 학생들은 자신의 웹 사이트를 가지고 있지요. 몇몇 학생들은 이 강의가 매우 어려울 것이라는 것을 알고 있습니다. 그래서 추가적인 도움이 필요할 것이고 매주 오피스 시간을 강의 웹사이트에 게재할 것입니다.  
 
그리고 이번 학기에 실습으로 과제를 제공할 것입니다. 실습과제를 하기 위해 가는 장소와 시간이 있고, 일반적으로 2명의 조교가 있을 것입니다. 그리고 과제를 하면서 필요하면 조교들로부터 도움을 얻을 수 있을 것입니다. 스케줄을 정해서 강좌 일정에 써놓을 것입니다. 보통은 일요일 오후 2시부터 4시까지거나 아니면 저녁이 될 것입니다. 제 생각에는 첫 번째 실습은 저녁인 것 같습니다. 그렇죠? 실습이 가까이 왔습니다. 가장 좋은 방법은 실습과제를 미리 하려고 노력하는 것입니다. 그러나 또, 도움이 필요하거나 사람들과 여러분의 솔루션에 대해 이야기 하고 싶다면 왜냐하면, 문제를 함께 의논할수록 여러분은 공동 작업 속에서 문제를 풀어낼 수 있기 때문입니다. 게다가 몇 개의 peer assistance 프로그램들도 있습니다. 또한 소수 교육 오피스도 지원프로그램을 가지고 있습니다. 그리고 보통은 매우 빨리 예약이 마감됩니다. 만약 여기에 흥미가 있으면, 그곳에 가서 약속을 잡는 것이 좋을 것입니다.  
 
실습과제, 저는 많은 사람들이 시도하고 시험해봤으면 좋겠네요. 우리는 이런 것을 해본 적이 없습니다. 다른 강의들은 잘 모르겠는데, MIT에서 이것을 했었던 강의가 있나요? 6.011이 했군요. 좋습니다. 좋아요. 그 수업에서 성공적이었나요? 안 갔다고요. 좋습니다. [웃음] 자 봅시다. 이것이 안 되면, 일반적인 오피스 아워를 이용하게 될 테지만, 몇몇 학생들에게 이것은 매우 좋은 기회일 것입니다. 만약 이 강의에 등록하고 싶다면 여러분은 반드시 웹 페이지에 등록해야 합니다. 이것은 요구조건이고 오늘 반드시 하셔야 합니다. 수업에 없으면 이 과목을 패스하기 어렵다는 것을 알게 될 것입니다. 드롭을 결정했다면 메일을 더 이상 보내지 않도록 여러분의 조교에게 알리고, 수업을 듣는 분들은 오늘 저녁 7시 전에 등록을 해야 합니다. 그러면 내일 정오가 되기 전에 여러분에게 설명시간 과제를 이메일로 보내게 될 것입니다. 그리고 만약 여러분이 목요일 정오까지도 이 이메일을 받지 못했다면 일반적으로는 그 강좌의 스태프에게 이메일을 보내주시기 바랍니다. 저에게 개인적으로 보내지는 마시고, 스태프에게 여러분이 설명시간 과제를 받지 못했다고 말씀해주시기 바랍니다. 목요일 정오까지도 받지 못하면 아마 밤이나 적어도 다음날 오전까지는 보내게 될 것입니다. 
 
좋습니다. SMA 학생들은 이것에 대해 걱정할 필요가 없습니다. 문제 세트들. 이번 학기에 할당된 과제는 9개가 있습니다. 문제 세트들에 대해 몇 가지 것들이 있습니다. 일반적으로 집에서 하는 과제는 받아주지 않을 것입니다. 만약 사정이 있다면 설명시간 강사님과 사전에 협의를 해야 할 것입니다. 사실 거의 모든 행정적인 일에 대해서는, 저한테 와서 늦게 내도 되냐고 묻지 마시고, 여러분의 설명시간 강사님과 상의하도록 하세요. 다른 것들도 읽어보시고, 그렇지만, 연습문제에 대해서는 언급해야겠군요. 연습문제를 풀기는 해야 하지만, 제출할 필요는 없습니다. 저는 연습문제를 푸는 것을 매우 추천합니다. 이런 것들은 모두 자료에 대한 이해를 테스트 하게 될 것입니다. 그리고 퀴즈를 푸는데 도움이 될 것입니다. 종종 알고리즘을 설명해 보라는 질문을 받습니다. 그리고 여기 여러분이 알고리즘을 설명하기 위해서 사용할 것들의 작은 아웃라인이 있습니다. 
 
성적은 어쨌든 제가 주게 되고 만약 문제를 빠뜨리게 되면 성적에 안 좋은 영향이 갈 것입니다. 성적은 알 수 없는 것이에요. 알았죠? 그렇지만 어떤 문제도 빠뜨리지 않게 되면 성적에 영향은 없을 것입니다. 만약 한 문제를 빠뜨렸다면, 성적에 대해 조정할 수 도 있습니다. 그렇지만, 이것들이 문제 세트는 아닙니다. 이것이 문제들인거죠. 그렇죠? 성적은 내려가게 될 것이고, 9이상을 하지 않으면, 일반적으로 3,4 문제세트들을 하지 않으면, 이 강의를 패스할 수 없습니다. 매년 해가 끝날 때 찾아와서 저는 어떤 문제도 없었고, 시험도 잘 봤는데, 패스 시켜주시면 안되나요? 라고 묻는 학생들이 있습니다. 저는 안 됩니다. 라고 말합니다. 매우 간단한 대답이지요. 왜냐하면 제가 계속 말해왔기 때문입니다. 문제 세트들은 이 강의에 필수 요소입니다.  
 
공동연구 방침에 대해 보도록 하지요. 이것은 매우 중요합니다. 모두 집중하도록 하세요. 만약 자고 있으면 일어나세요. 이게 누군가 깨울 것 같죠? [웃음] 과제의 목적에 대해서 말해보죠. Demaine 교수와 저의 철학은 집에서 하는 과제의 목적은 여러분의 이해를 돕기 위한 것이라고 생각합니다. 그리고 배우는 것을 돕는 한 가지 방법은 여러분이 막히지 않도록 하는 것이지요. 그리고 문제를 풀지 못하는 것이 없도록 하는 것입니다. 여러분은 함께 연구하게 되는 것이 좋습니다. 그러나 여기에는 공동연구에 대한 상식이 있는데, 만약 여러분이 가서 그저 다른 사람으로부터 정보를 얻는 정도까지만 하게 된다면 여러분은 잘 배울 수 없고, 시험을 잘 볼 수도 없을 것입니다. 제 경험에 비추어 보면, 일반적으로 공동연구를 해서 공부한 학생들이 혼자 공부한 학생들보다 잘했습니다.  
 
이것을 하는 것이 의무이고, 만약 여러분이 스터디 그룹에서 공부를 간다면, 여러분의 스터디 그룹 모임을 잘 준비하도록 하세요. 구체적으로 스터디 그룹에 가기 전에 각각의 문제에 대해서 여러분은 1시간 반이나 45분 정도 걸릴 것입니다. 그러면 기대한 정도의 속도에 도달하고, 여러분의 아이디어를 시험해 볼 수 있을 것입니다. 그러면 해결책을 얻을 수도 있고, 어떤 문제는 잘 풀리지 않았을 수도 있습니다. 그러나 적어도 그것에 전념하도록 하세요. 30분이나 45분 후에, 문제가 해결되지 않아서 그저 앉아서 머리를 치고 있지 마세요. 이것은 여러분의 시간을 생산적으로 사용하는 것이 아니죠. 그리고 저는 여러분이 시간이 있는데도 그러고 있다는 것을 알고 있습니다. 그렇죠? 그렇게 보이지는 않을지 모르지만요. 그래서 문제가 안 풀린다고 머리를 때리고 있지 말고, 그럴 때 스터디 그룹을 이용하도록 하세요. 스터디 그룹이 도와줄 것입니다.  
제가 언급한 것처럼, 실습과제가 있을 것이고, 어쩔 수 없이 그룹을 만들기 보다는 다른 학생들과 같이 연구하면서 공부할 기회가 있을 것입니다. 물론, 조교들도 그곳에 있을 것입니다. 
만약 여러분 그룹이 문제를 풀지 못하면, 옆의 그룹에 가거나 강사님께 여쭤보면 됩니다. 이렇게 문제를 풀어 가면 됩니다. 이미 해놓은 메모들을 바탕으로 문제 세트들을 기록하고, 그러나 이것은 여러분이 혼자 하도록 해야 합니다. 문제 솔루션은 다른 학생들과 함께 작성하지 마세요. 스스로 정리하도록 합니다. 알겠죠? 
 
그리고 여러분 문제 세트에 대해서 이것은 아카데믹한 부분이기 때문에 우리는 아카데믹한 정보에 대한 출처가 매우 중요합니다. 만약 여러분이 문제에 대해서 협동했다면, 협동한 사람들의 리스트를 작성해주십시오. 여러분의 성적에는 영향을 미치지 않습니다. 단지 알고자 하는 것입니다. 여러분이 교수님이나 조교에게 입으로 설명 못하는 문제 해결책을 제출하는 것은 방침의 위반입니다. 여러분이 제 레포트가 다른 사람의 것과 비슷합니다. 저는 베끼지 않았어요. 그러면 우리는 여러분에게 그 해결책에 대해 설명해 보라고 물을 겁니다. 만약 여러분이 못하면 이 방침에 따라서, 우리는 커닝이라고 간주할 것입니다. 이해 못한 것은 쓰지 못합니다. 여러분은 그것을 이해하고 쓸 수 있어야 합니다. 여러분이 작성한 것에 대해서 왜 그런지 이해하도록 하세요. 물론, 어떠한 협동도 시험에서는 허용되지 않습니다. 시험은 우리가 여러분을 평가하기 위함입니다. 그리고 저희는 다른 사람들을 평가하는 데에는 관심이 없지요. 우리는 여러분을 평가합니다. 그래서 시험에서는 어떠한 협동도 안 됩니다.  
 
우리는 집에서 풀어서 제출하는 두 번째 퀴즈가 있을 겁니다. 스케줄을 확인하고 만약 문제가 있으면 미리 알려주시기 바랍니다. 공동연구에 대해서는 월요일, 11월 28일 강의시간에 더 자세하게 이야기하도록 하겠습니다.  
 
일반적으로 여기서 강의가...의무적이지만, 9:30분이 조금 이른 것 같기는 합니다. 특히 월요일 또는 다른 요일에도요. 약간 일찍 일어 나야 하죠. 그렇지만 11월 28일 월요일에는 정각에 오지 않으면 시험을 잘 보지 못할 것입니다. 꼭 와야 하는 날이지요. 질문 있으신가요? 알겠죠? 정각에 꼭 와야 합니다. 인터넷 강의를 들어왔어도 말이죠. 만약 정 안 되겠다면, 가장 좋은 방법은 저희한테 오셔서 그것에 대해 이야기 하는 것입니다. 보통은 해결해드릴 수 있을 것입니다. 이것은 우리가 제 3자나 분명한 분석들에 의해서 누군가가 위반을 했다는 것을 알 때이고, 복잡해지겠죠. 그래서 여러분이 생각하기에 어떤 이유에 대해서 뭔가 잘못 한 것 같다 라고 생각하시면 저희한테 와서 이야기 하시면 됩니다. 사실 저희도 한때는 학생이었으니까요. 매우 오래되었지만요. 좋습니다. 질문 있습니까? 
 
자, 이 수업에는 정말 좋은 자료가 있습니다. 정말 멋진 자료죠. 정말 재미있습니다. 그렇지만, 여러분은 공부를 매우 열심히 해야 할 거에요. 자, 내용에 대해서 한번 이야기 해보죠.  
이것은 첫 번째 파트의 주제입니다. 이 강의의 첫 번째 파트는 분석에 초점을 맞추고 있지요. 두 번째 파트는 디자인에 초점을 맞추고 있습니다. 여러분이 디자인을 하기 전에 알고리즘을 분석하는 많은 기술들을 마스터 해야만 합니다. 그러면 여러분이 분석한 알고리즘을 효율적으로 디자인하는 위치에 도달하게 되는 거죠. 알고리즘 분석은 컴퓨터 프로그램 성능과 리소스 사용에 대한 이론적인 학문입니다. 그리고 특히 성능에 초점을 맞추죠. 우리는 컴퓨터를 어떻게 빠르게 만들지에 대해 공부합니다. 특히 컴퓨터 프로그램들이요. 우리는 또한 커뮤니케이션 같은 다른 리소스들에 대해서도 개발하고 이야기합니다.  
 
예를 들면 메모리에 대해서 말입니다. 램 메모리일수도 있고 디스크 메모리일수도 있지요. 여기에는 우리가 관심을 기울 어야 할 다른 리소스들이 있습니다. 그렇지만 우리는 주로 성능에 집중할 겁니다. 왜냐하면 이 강의가 성능에 관한 것이고, 저는 프로그래밍에서 성능보다 더 중요한 것이 뭐냐고 물으면서 시작하고 싶기 때문입니다. 만약 여러분이 엔지니어링 상황에서 코드를 쓰고, 소프트웨어를 작성하고 있다면 성능보다 더 중요한 것은 무엇일까요? 정확성(Correctness.) 좋습니다. 좋아요. 또 뭐가 있을까요? 간단함(Simplicity)도 될 수 있겠고요. 좋습니다. 유지(Maintainability)도 때론 성능보다 더 중요할 수 있지요. 비용(Cost). 어떤 유형의 비용이라고 생각하시나요? 아니, 제 말은 어떤 종류의 비용이 될 수 있을지에 대해 여쭤보는 것입니다. 우리는 소프트웨어에 대해 이야기하고 있지요. 그렇죠? 그래서 어떤 유형의 비용이 될 수 있을까요? 프로그래밍을 할 때 프로그래머 시간과 같은 몇몇 비용들이 있지요. 그래서 프로그래머의 시간(programmer time)이 또 다른 중요한 것이 될 수 있을 것입니다.  
 
안정성(Stability). 소프트웨어의 단단함. 또 뭐가 있을까요? 생각해 보세요. 여기 많은 엔지니어분들이 있는데... 엄청 많습니다. Features 는 어떤가요? 이것도 더 중요할 수 있죠. 기능성(Funtionality), 모듈방식(Modularity). 이것은 여러분이 코드에 부분적으로 변화를 준 방식대로 디자인되어지죠. 그리고 기능성에 단순한 변화를 주기 위해서 다른 코드로 변화를 줄 필요가 없습니다. 엄청 중요한 것이 하나 있습니다. 90년대에 컴퓨터에 아주 큰 부분이었는데. 아주 큰 것입니다. 음. 보안(Security) 좋습니다. 그건 쓰지도 않았네요. 보안(Security) 좋습니다. 그것은 사실 2000년대에 더 중요해지고 있죠. 보안은 종종 성능보다 더 중요합니다. 확장성(Scalability). 중요하죠. 확장성(Scalability)이 어느 부분에서는 성능과 관계 있지만, 확장성(Scalability)은 중요하죠. 큰 돌파구는 무엇이었을까요? 왜 사람들이 윈도우보다 매킨토시를 사용했을까요? 사용하기 쉬움(User-friendliness). 와우. 
 
만약 여러분이 90년대에 사용자 친화(user-friendliness으)로 된 컴퓨터 원들의 숫자를 세어보면, 이것이 전혀 없다가 현대에 컴퓨터가 사용자 친화적으로 되면서 현대 컴퓨터의 아주 중요한 부분으로 자리 잡게 되었다는 것을 알 수 있을 겁니다. 그래서 모든 이러한 것들이 성능보다 더 중요한 것들이지요. 이런 것들이 성능에 대해 이 강의에서 배우게 될 것들입니다.  
그러면 여러분은 왜 우리가 귀찮게 이런 많은 것들의 바닥에 자리 잡고 있는 알고리즘과 성능을 배워야 하죠? 라고 물을 것입니다. 항상 대부분 사람들은 차라리 성능보다 이런 것들을 배우고 싶다고 합니다. 나가서 사람들한테 물어보세요. 성능을 배우는 것이 나을까 아니면 사용자-친화(user-friendliness)를 배우는 것이 나을까? 항상 사람들은 성능보다 사용자 친화(user-friendliness)가 중요하다고 할 것입니다. 그러면 왜 우리는 이것을 공부 해야 하는가? 네 학생? 그것은 사용자 친화적이지 않습니다. 때때로 성능은 사용자 친화(user-friendliness)와 밀접한 연관이 있습니다. 매우 많이요. 어떠한 것도 앉아서 기다리는 것보다 더 좌절감을 느끼게 하는 것은 없을 것입니다. 그렇죠? 네. 좋은 이유입니다. 다른 이유도 있나요? 때때로 실시간 통제를 가지죠. 그래서 그것들이 적절하게 작동하지 않으면 사실 효과가 없습니다. 그렇죠? 이해하기 어려운데 음. 우리는 보통 사용자 친화(user-friendliness)를 수량화 하지 않습니다. 그래서 잘 모르겠네요. 그렇지만 무슨 말을 하는지는 이해합니다. 저 학생은 사용자 친화(user-friendliness)에서 기하급수적인 성능개선은 얻을 수 없음을 이야기 했습니다. 우리는 종종 성능에서 그 부분을 잘 이해 못하죠. 그런데 [웃음] 때때로 우리는 이해를 잘 못해요. 그러지만, 좋습니다.  
 
제가 중요하다고 생각하는 몇 가지 이유들이 있습니다. 우선 첫 번째는 성능은 종종 실현가능한지 실현 가능하지 않은지를 구분해줍니다. 우리는 이런 것들에 대해 들어왔지요. 예를 들어보면, 여기 실시간 요구(real-time requirements)가 있을 때, 그것이 충분히 빠르지 않다면 단순하게 정상적으로 동작하지 않을 것입니다. 또는 만약 너무나 많은 메모리를 사용하면, 또한 작동하지 않을 것입니다. 
 
결과적으로 여러분이 발견한 것은 기업가 활동의 최첨단에 있는 알고리즘들입니다. 만약 여러분이 사람들이 10년 전에 하던 재실행 일에 대해 이야기하는 것이라면, 성능은 그 수준에서 그리 중요하지 않습니다. 그러나 만약 여러분이 어떠한 사람도 전에 해본 적이 없는 일에 대해 이야기 하는 것이라면, 그 이유들 중에 하나는 시간이 너무 많이 걸려서 일 것입니다. 크기를 조정할 수 없고 기타 등등이 될 수 있죠 그래서 성능이 실현가능한지 실현 가능한지 나누는 하나의 이유입니다.  
 
또 다른 이유는 알고리즘이 여러분에게 프로그램의 움직임에 대해 이야기해주는 언어를 제공해주기 때문입니다. 그리고 결국 그것은 컴퓨터 과학 전반에 사용되는 언어가 됩니다. 이론적인 언어이고, 전문가들에 의해 쓰여 집니다. 왜냐하면 이것이 프로그램의 움직임을 깔끔하게 이해하는 방법이기 때문입니다. 그리고 성능에 대해 이해하는 좋은 방법이기 때문이죠. 그리고 이것이 이런 많은 것들의 가장 근본적인 부분에 있는 이유는... 약간 성능(Performance)이 돈과 같이 때문입니다. 통화 같아요. 여러분이 엄청 많은 돈이 있다면 무엇을 하는 것이 좋을까요? 음식을 가지는 것이 좋을까요? 물을 가지는 것이 좋을까요? 집을 가지는 것이 좋을까요? 어떤 것이든지요. 그리고 여러분은 기꺼이 백 달러짜리 계산서를 지불할 것입니다. 만약 여러분이 그러한 물품들에 대해 백 달러가 쓰여 있는 청구서를 받는다면 말이죠. 
 
비록 물이 여러분이 살아가는데 훨씬 더 중요하다고 하더라도 말이죠. 음 비슷하게, 성능은  
사용자 친화(user-friendliness)에 대해 지불하기 위해 사용되는 것입니다. 보안(Security)에 대해 지불하는 것이에요. 그리고 사람들이 이렇게 말하는 것을 들을 것입니다. 예를 들면, 제가 훨씬 더 기능(functionality)이 뛰어난 컴퓨터를 원한다고 하죠. 그러면 사람들은 자바로 프로그램을 만들 것입니다. C언어보다 훨씬 느린데 말이죠. 그리고 자바에서 프로그램 짜는데 성능 면에서 아마도 세 개정도의 요소를 가지기 때문이라고 말하죠.  
 
그러나 자바는 그럴만한 가치가 있다는 것입니다. 왜냐하면 자바는 객체 지향적이라든지 많은 장점을 지녔기 때문입니다. 메커니즘이나 기타 등등 을 제외하면 말이죠. 그래서 사람들은 성능 면에서 기꺼이 세 개중의 하나의 요소에 대해서도 지불을 하는 것입니다. 이것이 바로 여러분이 성능을 원하는 이유입니다. 알겠죠? 여러분이 원하는 다른 것들을 지불하기 위해 사용할 수 있기 때문입니다. 이것이 어떤 면에서, 많은 요소들의 가장 아랫부분에 위치하는 이유이기도 하지요. 왜냐하면 여러분이 수량화 할 수 있는 가장 보편적인 것이기 때문입니다.  
 
여러분은 두 개 중에 하나의 요소에 돈을 지불하고 싶으신가요? 아니면 보안 같은 것들에 대해 세 개 중에 하나에 돈을 지불하고 싶으신가요? 그리고 게다가 이러한 교훈들은 커뮤니케이션, 메모리 같은 리소스 측정에 대해서도 일반화 됩니다. 그리고 우리가 알고리즘 성능을 공부하는 마지막 이유는 정말 재미있기 때문입니다. 스피드는 항상 즐겁죠. 그렇죠? 왜 여러분은 차, 경주마 같은 것들을 빠르게 타나요? 
 
로켓 같은 것들... 우리는 왜 그렇게 하죠? 스피드는 즐겁기 때문입니다. 스키. 스키 좋아하나요? 저는 스키를 좋아합니다. 스키 타고 빨리 내려가는 것을 좋아하죠. 정말 재미있습니다. 하키. 빠른 스포츠죠. 그렇죠? 우리는 모두 빠른 스포츠를 좋아하죠. 모두 다는 아니겠지만, 좋아요. 넘어갑시다. 우리가 알고리즘을 왜 공부하는지에 대한 약간의 개념에 대한 것이었습니다. 우리가 생각할 것들에 대한 기본을 쌓는 것입니다.  
 
그래서 우리는 컴퓨터 계산에서 스스로가 어떻게 돈을 만들어 내는 지를 이해하고 싶습니다. 매우 간단한 문제로 시작하도록 하죠. 알고리즘에서 매우 오랫동안 연구되어온 것들 중에 하나입니다. 정렬의(sorting) 문제이죠. 앞으로 몇 개의 강의 동안 이것에 대해 공부할 것입니다. 왜냐하면 정렬(sorting)이 매우 많은 알고리즘적인 기술을 포함하기 때문입니다. 정렬(sorting)문제는 다음과 같습니다. 입력(input)으로는 a1, a2에서 an까지 숫자 시퀀스(sequence)가 있습니다. 그리고 출력(output)은 이런 수들의 순열입니다.  
 
수열은 숫자들의 재배열입니다. 모든 숫자들은 숫자가 커지는 것을 만족하면서 딱 한번 씩만 나오게 됩니다. 저는 ‘such that’ 의 의미로 종종 달러 표시를 씁니다. 많은 숫자를 가지고, 적절하게 넣습니다. 여기 그것을 해줄 알고리즘이 있습니다. 삽입정렬이라고 부릅니다. 우리가 의사코드(pseudocode)라고 부르는 것으로 이 알고리즘을 써보도록 하겠습니다. 의사코드는 약간 프로그래밍 언어 같은 것입니다. 이것은 간단하게 쓴 것입니다.  
 
이 sorts A는 1부터 n까지 입니다. 그리고 여기 삽입정렬에 대한 코드가 있습니다. 이것이 의사코드(pseudocode)라 부르는 것입니다. 그리고 만약 의사코드(pseudocode)를 이해하지 못하면 여러분은 어떠한 표기법(notation)에 대해서도 질문하셔도 됩니다. 시간이 갈수록 익숙해지실 겁니다. 의사코드(pseudocode)에서 우리는 들여쓰기(indentation)를 사용합니다. 모든 언어는 처음과 끝을 표시하는 구분문자를 가지고 있습니다. 예를 들면 자바나 C언어에서 {}같은 것처럼 말이죠.  
 
우리는 단지 들여쓰기만 사용합니다. 의사코드의 아이디어는 각각의 단계를 이해하는 동안은 가능 한한 짧게 해서 알고리즘을 이해하도록 하는데 있습니다. 실제로 이런 것들의 묶음을 보여주는 의도로 들여쓰기를 사용하는 언어도 있었습니다. 일반적으로는 안 좋은 생각이죠. 왜냐하면 한 페이지 넘어가면, 예를 들면 이 묶음의 단계가 어디까지인지 알 수가 없으니까요  
 
반면에, 딱 구분되는 중괄호는 말하기가 훨씬 쉽지요. 이것이 여러분이 소프트웨어 엔지니어링에서 들여쓰기 사용법이 안 좋은 이유입니다. 그러나 짧게 할 수 있고, 조금만 써도 되니까, 우리한테는 매우 좋죠. 이것이 삽입 정렬(insertion sort)입니다. 이것이 어떻게 작동하는지 좀 알아보도록 하죠. 기본적으로 배열A를 가지고, 어느 한 지점에서, 바깥 루프는 j에서, 2에서 n으로 움직이고, 안의 루프는 j-1에서 시작해서 0이 될 때까지 실행합니다. 
 
기본적으로 만약 우리가 알고리즘에서 어떤 지점을 보면 우리는 j가 있는 것을 보게 됩니다. 배열A의 j. j번째 원소. 우리가 가장 기본적으로 해야 할 것은 우리가 키(key)라고 부르는 여기서 값을 빼내는 것입니다. 그리고 이 부분이 가장 중요한 부분입니다. 금요일 설명시간에 이것에 대해 더 이야기 나눠보도록 하죠. 매 시간에 이 루프에 의해서 그대로 유지되는 불변성(invariant)이 있습니다.  
 
그 불변(invariant)은 이 배열의 이 부분이 정렬되는 것입니다. 그리고 매 시간 루프를 통과하면서 목표는 증가하는 것. 정렬 되어진 이 부분에 하나 더해지는 것입니다. 그리고 우리가 key를 빼냈던 그 방식대로 해서 값을 복사해서 이렇게 올려주는 것입니다. 그리고 키(key) 가 가려고 했던 곳에 도달 할 때까지 계속 복사를 하다가 그 자리에 키(key)를 삽입(insert)하는 것입니다. 이것이 우리가 삽입정렬(insertions sort)라고 부르는 이유입니다. 키(key)가 들어갈 곳을 찾을 때까지 이것들을 옮기고, 복사해서 한 칸씩 옮기고 이곳에 키(key)를 넣으면 되는 것입니다. 그러면 A에서 1부터 j까지 정렬 되어 지고, j+1에서 작동합니다. 
 
예를 하나 보겠습니다. 8,2,4,9,3,6 이 있다고 합니다. 2에서 시작합니다. J는 2와 같습니다. 2가 여기에 삽입되어야 되니까, 2,8,4,9,3,6이 됩니다. 그리고 4를 봅니다. 4는 여기 앞으로 가야 되니까, 바깥 루프가 2번 반복된 후에 2,4,8,9,3,6이 됩니다. 그 다음 9를 봅니다. 우리는 9가 바로 그 자리라는 것을 알 수 있습니다. 이 단계에서는 별로 할 일이 없죠. 그러면 반복 후에 우리는 정확하게 똑같은 출력결과를 갖게 됩니다. 그 다음 3을 봅니다. 3은 이곳에 삽입되어야 합니다.  
 
2,3,4,8,9,6입니다. 그리고 마지막으로 6을 보고 6은 이곳으로 삽입되어야 하니까, 2,3,4,6,8,9가 됩니다. 이제 다 됐습니다. 질문 있습니까? 배열은 처음에 1에서 시작하는 것이 맞습니다. 네. A[1...n]. 그렇죠? 이것이 삽입 정렬(insertions sort) 알고리즘입니다. 그리고 이것이 우리가 분석한 첫 번째 알고리즘이군요. 알고리즘 분석을 돕기 위해 수학 지식을 이용하게 될 것입니다. 무엇보다도, 러닝 타임(running time)에 대해서 보도록 하죠.  
 
러닝 타임(running time)은 많은 요소에 의해 결정됩니다. 한 가지는 입력(input)입니다. 예를 들면 입력(input)값들이 이미 정렬이 되어 있으면 삽입 정렬(insertion sort)은 할 일이 거의 없습니다. 매 시간 이런 경우와 같을 것이기 때문입니다. 이미 정렬이 돼서 제 자리에 있기 때문에 앞으로 하나씩 이동할 필요가 없는 것이죠. 반면에 삽입정렬(insertions sort)의 최악의 경우(worst case)는 어떻게 될까요? 만약 이것이 반대면, 할 일이 정말 많아지는 거죠. 바깥 루프의 매 단계에서 계속해서 앞으로 이동하는 과정이 필요하게 됩니다.  
 
실제 입력(input)값 외에도 러닝타임은 물론 입력의 사이즈에도 영향을 받습니다. 여기 예가 있습니다. 우리가 6개의 입력이 있는 경우를 다루었지요. 예로 만약 6*10^9의 입력 값을 다루게 된다면 시간이 더 오래 걸릴 것입니다. 만약 더 많은 입력 값들을 정렬하게 된다면, 시간은 점점 더 많이 걸리겠지요.  
 
전형적으로, 우리가 그것들을 다루는 방식은 입력 사이즈에서 그것들을 파라미터(parameter)로 나타내는 것입니다. 우리는 우리가 정렬하는 것들의 사이즈에 대해 함수를 이용해 시간에 대해 이야기 나누게 될 것입니다. 그래서 그것의 움직임에 대해 볼 수 있게 될 것입니다. 그리고 마지막으로 러닝 타임(running time)에 대해서 말하고 싶은 것은 우리가 러닝 타임(running time)에서 상한(upper bound)을 알고자 한다는 것입니다.  
 
우리는 그 시간이 어느 정도 이상은 아니라는 것을 알고자 합니다. 그리고 그 이유는 사용자에게 품질 보장을 하는 것이기 때문입니다. 만약 제가 이것은 작동하지 않을 것입니다 라고 말한다면, 예를 들면, 제가 여러분에게 여기 프로그램이 하나 있고, 이것이 작동하는데 3초 보다 더 걸리지는 않을 것이라고 말한다고 하면 그것은 여러분에게 그것을 어떻게 사용해야 하는지에 대한 진짜 정보를 주는 것이지요. 예를 들면 실시간 세팅에서 말이죠. 반면에, 제가 여기 프로그램이 하나 있고, 이것인 적어도 3초 안에 작동하게 될 것이다라고 말한다면, 이 프로그램이 3년이 걸릴지는 모르는 것입니다. 여러분이 그 컴퓨터의 사용자라면 보장 받을 수 없다는 것입니다. 일반적으로 우리는 상한(upper bound)을 원합니다. 왜냐하면 이것이 사용자에게 보장한 것을 보여줄 수 있기 때문입니다.  
 
다른 종류의 분석방법이 있습니다. 첫 번째로 우리가 집중 해야 할 것은 최악의 경우(worst-case)입니다. 그리고 보통은 어떠한 입력 사이즈에 대해서도 최대시간이 되는 것이라고 정의합니다.(T(n)). 그것이 하는 일은 만약 때때로 입력이 좋고 그리고 때때로 입력이 나쁠 때에 우리는 최악의 경우(worst case)를 생각해야 한다는 말입니다. 왜냐하면 그것이 우리가 보장할 수 있는 방법이기 때문입니다.  
 
이것은 단지 때때로 하는 것이 아니라, 항상 하는 것입니다. 그래서 우리는 최대 시간을 보게 될 것입니다. 최대가 없다면, T(n)이 어떤 점에서 관계라는 것을 명심하세요. 함수가 아니라 관계를 나타내는 것입니다. 왜냐하면 시간이 입력 사이즈에 의존하기 때문입니다. 많은 다른 시간들을 얻을 수 있지요. 그러나 최대를 넣으면 관계는 하나의 함수로 변합니다. 왜냐하면 그것이 가질 수 있는 최대 시간은 단지 하나이기 때문입니다. 알겠죠? 
 
때때로 우리는 average case에 대해서도 이야기 합니다. 때때로 이것을 사용하죠. T(n)은  
사이즈가 n인 입력(input) 전반적으로 기대되는 시간에 대한 것입니다. 이것은 기대되는 시간(expected time)이지요. 그러면, 제가 기대되는 시간에 대해 이야기하면 또 다른 것은 무엇을 말해야 할까요? 기대되는 시간이 무슨 뜻일까요? 죄송한데 손들어 주시겠습니까? 기대 입력(expected inputs). 기대입력은 무슨 뜻일까요? 수학이 좀 더 필요하네요. 여기 기대 시간에 무엇이 필요 할까요? 모든 입력(input)의 시간을 구해서 평균을 낸다. 좋습니다. 그것이 기대시간으로 우리가 의미했던 것과 가깝네요. 좋습니다. 딱 맞지는 않는데, 여러분이 말하는 것은 완벽하게 맞는 것이어야 합니다.  
 
네, 학생? 모든 입력 값을 넣었을 때의 시간, 하나의 입력 값을 넣었을 때의 기대되는 확률. 평균에 가중치를 둔 생각이네요. 정확하게 맞습니다. 어떻게 모든 입력 값(input)들의 확률이 무엇인지 알았을까요? 어떻게 이 주어진 상황에서 특정 입력 값(input)의 확률을 알아냈을까요? 모릅니다. 추정해야만 합니다. 그런 추정을 뭐라고 부르죠? 이것을 충족시키기 위해서 어떤 추정방법을 사용해야 하죠? 통계적 분포의 추정이 필요합니다.  
 
그렇지 않으면 기대 시간은 어떠한 의미도 뜻하지 않습니다. 왜냐하면 확률을 모르기 때문입니다. 확률을 하기 위해서 여러분은 추정이 필요하고 이러한 추정을 분명하게 말해야 합니다. 가장 보편적인 추정 중에 하나는 모든 입력이 동등하게 비슷한 것입니다. 이것을 균일 분포라고 부릅니다.  
 
그러나 여러분이 추정할 수 있는 다른 방법들도 있습니다. 그리고 그것들은 모두 사실이 아닐 수도 있습니다. 이것은 좀 더 복잡한데, 여러분이 보다시피, 다행스럽게도, 여러분 모두가 좋은 확률 지식을 가지고 있기 때문에 우리는 평균 같은 것들을 다루는 주제를 말하는데, 어려움을 느끼지 않을 것입니다.  
 
그렇지 않더라도, 시간이 흐르면 이해하게 될 겁니다. 이 수업 선수과목인 확률 수업을 듣는게 좋을 거에요. 마지막으로 제가 언급할 것은 best-case 분석입니다. 이것을 가짜라고 주장하죠. 가짜에요. 좋지 않습니다. 왜 best-case 분석을 가짜라고 할까요? 
 
best-case 는 아마도 발생하지 않았을 것입니다. 사실 흥미로운데, 정렬문제에 있어서 정렬 되어 진 가장 평범한 것들은 재미있게도 이미 정렬되어진 것들 이었습니다. 또는 적어도 거의 정렬 되어져 있었거나 말이죠. 예를 들면 정렬 되어진 가장 흔한 것들 중에 하나는 숫자를 검사하는 것입니다. 그것들은 들어와서 같은 순서로 쓰여 지는 경향이 있죠.  
 
거의 정렬 되어진 것들을 정렬하죠. 제 말은, 좋습니다. 보장(guarantee)하고 싶죠. 왜 이것이 보장(guarantee)이죠? 뭔가 알아낼 듯 하네요. 그렇지만, 이 부분에서 좀 더 자세하게 봐줘야 합니다. 제가 어떻게 속였죠? 여러분도 속일 수 있죠. 여러분이 원하는 어떤 느린 알고리즘을 가지고 특정 입력(input)을 검사하죠. 그리고 그 입력(input)이 딱 적당하면, 즉시 맞았다고 하면서 이게 답이라고 하겠죠. 하나의 좋은 best-case를 얻은 겁니다.  
 
그러나 엄청나게 많은 수에 대해서는 어떻게 진행되는지 뭐라고 말해줄 수가 없습니다. 그래서 특정 입력(input)에서만 빠르게 작동하는 느린 알고리즘으로 속일 수가 있는 것이죠. 여러분이 할 일은 많지 않으니 보통 걱정하지 않아도 됩니다. 자. 삽입 정렬(insertion sort)의 최악의 경우 시간( worst-case time)은 무엇인지 한번 볼까요? 
 
자, 약간 재미있는 주제로 들어가 보겠습니다. 첫 번째로, 삽입정렬의 최악의 경우 시간(worst-case time)은 여러분이 돌리고 있는 컴퓨터에 따라 다릅니다. 누구의 컴퓨터 인가요? 큰 슈퍼 컴퓨터 인가요? 아니면 손목시계인가요? 그것들은 다른 계산 능력을 가집니다.  
 
그리고 알고리즘을 비교할 때, 우리는 일반적으로 상대적 속도(relative speed)에 대해서 비교합니다. 같은 기계에서 2개의 알고리즘을 비교합니다. 여러분은 단지 알고리즘의 상대적인 속도만 비교하는데, 같은 기계에서 비교할 필요가 있냐고 물을 수도 있습니다. 물론, 절대적인 속도(absolute speed)에도 관심이 있을지도 모릅니다. 사실 어떤 기계에서 돌리느냐에 상관없이 알고리즘이 좋을까요? 
 
그리고 이것은 제가 하드웨어에 대해 말하지 않고, 소프트웨어 알고리즘의 최악의 경우 시간(worst-case time)에 대해 이야기해서 약간의 혼란을 줄 수 있습니다. 왜냐하면 분명히, 제가 빠른 기계에서 알고리즘을 돌린다면, 빨리 돌아갈 것입니다. 그래서 이 부분이 여러분이 알고리즘에 대한 큰 생각을 얻는 부분이기도 합니다.  
 
왜 알고리즘이 그러한 큰 분야가 되었을까요? 왜 알고리즘은 구글, 아카마이, 아마존 같은 큰 기업을 낳았을 까요? 왜 알고리즘 분석은 컴퓨팅 역사 전반에 걸쳐 큰 성공을 이루었을까요? 그리고 완전히 통달하게 되는 능력이고, 정말 어지럽고, 복잡한 상황을 계산해 내서 수학을 쓸 수 있도록 줄이는 능력이 되는 걸까요? 그 아이디어를 우리는 점근적 분석(asymptotic analysis)이라고 부릅니다.  
 
점근적 분석의 가장 기본적인 생각은 기계 의존적인 상수들을 무시하는 것입니다. 그리고 진짜 러닝 타임(running time)대신에, 러닝 타임의 증가(the growth of the running time)을 보는 것입니다. 진짜 러닝 타임(running time)은 보지 않습니다. 러닝 타임의 증가(growth)를 봅니다. 그것이 의미하는 바를 알아봅시다. 정말 좋은 생각입니다. 어려운 게 아닙니다. 그렇지 않으면, 첫 번째 수업 시간에 가르치지는 않았을 것입니다. 그렇지만, 매우 중요한 개념이고, 앞으로 몇 번의 강의 시간에 그것이 의미하는 바에 대해 공부하게 될 것입니다. 
 
그리고 여러분이 엔지니어로 일하게 되면, 매일 쓰게 될 것입니다. 그러기 위해서, 우리는 몇몇 표기법을 사용하게 될 것입니다. 특히 점근적 표기법(asymptotic notation)을 사용할 것입니다. 이미 몇몇 분들은 표기법을 보았을 수도 있고, 아직 보지 못한 분들도 있을 것입니다. 그러나 조금은 봤어야 하죠. 우리가 수업에서 주로 사용하게 될 표기법은 세타 표기법(theta notation)입니다.  
 
세타 표기법(theta notation)은 배우기가 매우 쉽습니다. 공식을 만들고, 낮은 차수의 항과 최고차 항을 이끄는 상수를 지워주면 됩니다. 예를 들면, 3n^3 = 90n^2 - 5n + 6046 공식이 있다고 하면, 우리가 지워줄 수 있는 항들은 무엇입니까? n^3이 n^2보다 크니까, 이 항들을 무시해주고, 그리고 θ(n^3)이라고 말할 수 있는 거죠. 매우 쉽습니다.  
 
이것이 세타 표기법(theta notation)입니다. 자, 이것은 세타 표기법(theta notation)의 엔지니어링 조작방법이고, 여기에는 사실 수학적 정의가 있습니다. 그것은 다음 시간에 이야기 하도록 할 것입니다. 함수의 집합에 관한 정의에 관한 것입니다. 여러분은 수학과 컴퓨터 과학 수업 모두에 책임감을 느끼게 될 것입니다.  
 
과정 전반에 걸쳐, 수학과 엔지니어링 상식에 어려움을 느낄 수 있습니다. 이것은 엔지니어링 과정이고, 우리는 모두 하게 될 것입니다. 이것이 여러분이 하는 것들을 이해하는 엔지니어링 방법이고, 그래서 이러한 조작을 할 수 있어야 합니다. 또한, 세타 개념의 수학적 정의를 이해해야 합니다. 그리고 그것과 관계된 빅오 표기법(O notation)과 오메가 표기법(omega notation.)에 대해서도 알아야 합니다.  
 
n이 무한대로 간다고 할 때, θ (n^2)알고리즘은 결과적으로 항상 θ (n^3)을 이기게 됩니다. n이 점점 커질수록, 만약 제가 이 식의 완전히 정확한 행동을 계산해 내어도, 이 다른 항들이 어떤지는 그리 문제가 되지 않습니다. θ(n^2)알고리즘이 있다면 이것은 항상 θ(n^3)알고리즘보다 빠르게 돌아갈 것입니다. 이 아래 항들이 무엇이어도 상관이 없습니다. n^3의 계수가 무엇이든 상관이 없습니다. 이것이(θ (n^2))이 항상 빠를 것입니다.  
 
심지어 θ (n^2)알고리즘이 느린 컴퓨터에서 돌아가고, θ (n^3)이 빠른 컴퓨터에서 돌아간다고 해도, 점근적 표기법(asymptotic notation)이 좋은 것은 상대적이고, 절대적인 스피드를 비교하는 우리의 문제를 해결해 준다는 것이죠. 왜냐하면 우리는 컴퓨터가 어떻든지, 플랫폼이 어떻든지 간에 이것을 할 수 있기 때문입니다.  
 
다른 플랫폼에서, 다른 상수들을 얻을지도 모릅니다. 진짜 러닝 타임(running time)의 기계 의존적인 상수들 말입니다. 그렇지만, 만약 입력(input)의 크기가 커짐에 따라 커지는 정도를 보면, 점근적 분석이 일반적으로 변하지 않는 것을 볼 수 있을 것입니다. 예를 들면, 그림으로 설명 드리겠습니다. x축은 n으로 놓고, y 축은 T(n)으로 놓겠습니다.  
 
그러면, 이 곡선이 θ (n^3)알고리즘이 될 것이고, 이 곡선이 θ (n^2)알고리즘이 될 것입니다. 그리고 항상 두 알고리즘의 교차점이 n_o가 생기게 됩니다. 여러분이 가지고 있는 컴퓨터의 스피드에 대해 시작점에서 θ (n^2)가 θ (n^3)보다 유리했을지라도, n_o보다 큰 지역에서 θ (n^2)알고리즘은 θ (n^3)알고리즘보다 작을 것입니다.  
 
그러면 엔지니어링 관점에서 보도록 하죠. 우리가 다루어야 할 몇 가지 문제가 있습니다. 왜냐하면 때때로 n_o는 컴퓨터가 그 문제를 해결하지 못할 만큼 매우 클 수 있기 때문입니다. 그럼에도 불구하고, 우리가 느린 알고리즘에 관심을 가지는 이유는 느린 알고리즘들은 점근적으로는 느려지겠지만, 적당한 크기의 입력 크기(input size)가 들어온다면 더 빠를 것이기 때문입니다.  
 
그래서 우리는 좋은 프로그래밍을 하기 위해서 수학적 이해와 엔지니어링 상식 사이의 균형을 맞춰 공부해야 합니다. 그래서 그냥 알고리즘 분석을 끝내서는 여러분은 좋은 프로그래머가 될 수 없을 것입니다. 프로그램을 어떻게 짜는지에 대해서 배워야 하고, 그것들이 관련이 있을 때와 없을 때를 이해하기 위해 실제로 이러한 도구들을 사용하여 연습해 보아야 합니다.  
 
훌륭한 프로그래머가 되고 싶으면, 2년 동안 매일 프로그램을 만들면 됩니다. 그러면 훌륭한 프로그래머가 될 거에요. 만약 세계적인 프로그래머가 되고 싶으면, 10년 동안 매일 프로그램을 만들면 됩니다. 아니면 2년 동안 매일 프로그램을 찌면서 알고리즘 수업을 들으면 되죠. 우리가 했던 삽입 정렬(insertion sort) 알고리즘으로 돌아가 봅시다. 삽입정렬 알고리즘 분석을 해볼 겁니다. 최악의 경우(worst-case)를 볼까요? 이것은 우리가 전에 언급했다시피, 입력(input)이 반대로 정렬될 때를 말합니다. 가장 큰 원소가 첫 번째에 오고 가장 작은 것이 마지막에 위치하죠. 삽입될 때마다 모든 것들이 이동하게 됩니다.  
 
루프를 보면, 러닝 타임(running time)을 적을 수 있습니다. 우리는 요약을 하면 됩니다. 우리는 모든 작동(operation), 모든 기본적인 작동(operation)에 일정한 시간이 걸린다고 가정하면 됩니다. 그러나 그 일정한 시간에 대해서 걱정할 필요는 없습니다. 왜냐하면 우리는 점근적 분석법을 이용할 것이기 때문입니다. 제가 말했다시피, 이 방법의 좋은 점은 모든 이러한 것들을 약간 무시할 수 있게 해준다는 데에 있습니다.  
 
3 밀리미터 같은 곳이 아니라, 30,000 피트에서 내려다 보는 것과 같은 거죠. 이 각각의 작동들은 가장 기본적인 작동(operation)이 될 것 입니다. 작동(operation)을 세는 것에 있어서 첫 번째로 고려해야 할은 참조 메모리를 세는 것입니다. 실제로 변수에 몇 번 접근하게 될까요? 이 모델에 대해서 생각하는 약간 다른 방법입니다.  
 
우리가 그것을 하면, 이 루프를 통과하게 될 것입니다. j는 2에서 n으로 가고 우리는 그 루프 내에서 한 일을 추가하게 될 것입니다. 수학적으로 j가 2에서부터 n까지 갈 때의 합을 구할 수 있습니다. 이 루프 안에서 진행해 가면서 무슨 일이 일어날까요? 음, 이 루프 안에서 일어나는 일은 다양할 겁니다. 그러나 최악이 경우(worst case)에, 얼마나 많은 작동(operation)들이 각각의 j 값에 대해서 어떻게 진행해 나가게 될까요? 
 
주어진 j값에 대해, 이 루프 안에서 얼마나 많은 동작이 일어나게 될까요? 누가 말해보겠습니까? 점근적으로, 그것이 theta j 입니다. 이 루프가 1에서 j-1이 되므로, 여기서 theta j가 일어나게 됩니다. 그리고 각각의 단계의 i값에 대해 일정한 양의 일을 하게 되고, i는 j-1에서 0로 떨어지게 됩니다. 그래서 우리는 θ (j)라고 말하게 됩니다. 여러분 이해하겠어요? 
 
좋습니다. 계산할 공식이 있습니다. 이 공식을 단순하게 하고 싶다면, 답은 무엇일까요? 미안합니다. 뒤쪽이요. 네, 좋습니다. θ (n^2), 좋습니다. 왜냐하면, 이것은 연속된 숫자의 합이기 때문입니다. 무슨 뜻인지 알겠습니까? 수학적 용어들에 대해 알아야 우리가 의사소통 할 수 있지 않겠어요? 이런 것들을 알아야 합니다. 그래야 이야기 할 수 있어요. 이것은 어떤 종류의 시퀀스로 불리나요? 이것은 사실 급수인데, 좋습니다. 어떤 종류의 급수 일까요? 등차 급수. 와, 좋습니다. 의사 소통할 수 있는 예리한 학생이 있네요.  
 
이것은 등차 급수입니다. 기본적으로 1 + 2 + 3 + 4 로 더해지게 되고, 거기에는 몇몇 상수들도 있을 수 있지만, 기본적으로 n까지 1 + 2 + 3 + 4 + 5 + 6로 더해지게 될 것입니다. 그것이 θ (n^2)입니다. 만약 이 수학을 모르면, 책에 단원이 있고, 아니면, 선수과목을 들었어야 했죠.! 등차수열... 기억이 날 듯 말 듯 하죠? 네네, 좋습니다. 이 조작방법에 대해서 알아두어야 하고, 다음시간에도 좀 더 볼 것입니다. 그렇지만, Theta 가 어떻게 작동하는지에 대한 Theta 조작법을 꼭 알아두도록 합니다. theta는 약한 표기법입니다. 미적분학에 나오는 라이프니츠 표기법과 같은 것이 강한 표기법이죠. 연쇄 법칙(chain rule)은 단지 2개를 지워주면 됩니다.  
 
연쇄법칙에서 없어지는 것은 정말 멋집니다. 라이프니츠 표기법에서는 조작하는 방법이 너무나 직접적으로 보여 집니다. 세타 표기법은 그렇지 않습니다. 여러분이 어려움에 빠졌다고 생각이 든다면, 세타 표기법에서 어떻게 되어가고 있는 것인지 다시 한번 잘 생각해 보아야 합니다. 이것은 조작이 쉬운 표기법이기 보다는 설명적인 표기법이라고 하겠습니다. 이것을 가지고 할 수 있는 많은 조작법들이 있습니다. 그러나 세타 표기법(theta notation)이 어떻게 구해지는지 이해하지 못한다면 앞으로 하는 것을 이해하는데 어려움을 느낄 것입니다.  
 
세타 표기법에 대해서는 다음 시간에 더 이야기 하도록 하죠. 삽입 정렬(insertion sort)은 빠를까요? 음, 입력 n의 개수가 적을 때는 적당히 빠르지만, 입력 n의 개수가 많으면 전혀 그렇지 않습니다. 삽입 정렬보다 좀 더 빠른 알고리즘을 보여드리죠. 이것은 합병 정렬(merge sort)이라고 불립니다. 삽입 정렬(insertion sort)를 남겨둬야 할지 고민이군요. 지우겠습니다. 이 부분은 나중에 쓰도록 하겠습니다. 공책에 적을 때 왼쪽에 공간을 좀 남겨두세요. 이것이 합병 정렬(merge sort)입니다. 배열 A에 1부터 n까지 있고요.  
 
기본적으로 3단계가 있습니다. 만약 원소가 1개이면, 우리는 이미 정렬이 끝났습니다. 하나의 원소를 정렬한 것이죠. 이미 되었네요. 좋습니다. 재귀 알고리즘. 그렇지 않으면, 우리는 재귀적으로 A를 1부터 ⌈n/2⌉까지 정렬하고, ⌈n/2⌉+1부터 n까지를 정렬합니다. 그래서 입력 값들은 두 부분으로 나누어 집니다. 그리고 나서 세 번째로, 우리가 이미 정렬을 마친 두 부분을 합치도록(merge) 합니다. 
 
그것을 하기 위해서, 우리는 서브 루틴(subroutine)을 사용합니다. 제가 보여드리죠. 여기 서브 루틴이 있습니다. 이렇게 작동합니다. 2개의 리스트가 있고, 그것들 중 하나를 20이라고 말하도록 하겠습니다. 반대 순서로 하고 있습니다. 이렇게 정렬했습니다. 그리고 나서 다른 한 개의 서브 루틴을 정렬합니다. 왜 이 순서로 하는지는 모르겠지만, 어쨌든 여기에 또 다른 리스트가 있습니다. 제가 정렬한 2개의 리스트들이 있습니다. A[1]부터 A[⌈n/2⌉]까지, A[⌈n/2⌉+1]부터 A[n]까지 입니다.  
 
제가 처음으로 해야 할 일은 이미 정렬된 2개의 리스트 중 가장 작은 원소가 있는 곳을 찾는 것입니다. 첫 번째 리스트의 헤드(head)에 있을까요? 아니면 두 번째 리스트의 헤드(head)에 있을까요? 2개의 원소를 봅시다. 어떤 원소가 더 작나요? 이것이 더 작지요. 
 
그러고 나면 해야 할 일은 더 작은 원소를 출력 배열(output array)에 넣어주는 것입니다. 그리고 지워줍니다. 그 다음에 작은 원소는 어디에 있을까요? 그 답은 2개의 리스트들 중 하나의 헤드(head)에 있을 것입니다. 그러면 저는 이것을 지우고 출력 배열(output array)에 넣어주고, 다음 7을 동그라미 쳐줄 것입니다. 7과 9중 7이 더 작으니 7을 출력 배열(output array)에 넣어주고, 다음 원소를 동그라미 쳐 줍니다. 다음에는 9와 13을 보게 되고 그래서 각각의 단계에서 배열의 크기와는 상관없이 모든 단계는 몇몇의 고정된 동작 횟수를 가지게 됩니다.  
 
각각의 단계에서 첫 번째로 2개의 원소를 보고, 작은 것을 고른 다음, 제가 현재 리스트의 헤드(head)를 알 수 있도록 포인터를 배열로 옮기는 것입니다. 그러므로 그 시간은 전체 원소 개수 n에 'n'이 됩니다. 우리는 이것을 때때로 선형 시간(linear time)이라고 부릅니다. 2차나 다른 것이 아니기 때문입니다. 이것은 n에 비례합니다. 입력 크기(input size)에 비례합니다. 그것이 선형 시간입니다. 쭉 살펴보면서, 이 간단한 작동(operation)을 해보면, 결국 n 작동(operation)이 되는 것입니다.  
 
따라오고 있지요? 좋습니다. 그래서 이것이 재귀 프로그램인 것입니다. 이 프로그램에 대해서 반복을 써볼 수 있습니다. n 원소를 정렬한 시간을 T(n)이라고 해 봅시다. 1개의 스텝을 실행하는데 얼마나 걸릴까요? 일정한 시간입니다. n이 1인지 한번 확인해 봅시다. n의 사이즈는 독립적입니다. 기계가 무엇이든지 간에 일정한 양의 기계어 명령을 취할 것이고, 우리는 그것을 상수 시간(constant time)이라고 부릅니다. θ (1)이라고 부르죠.  
 
이것은 사실 약간은 남용입니다. 그리고 일반적으로 그 이유를 말하기 위해서는, 무엇과 함께 커졌는지 말해야만 합니다. 그러나 우리는 그저 상수를 의미하는 표기법으로 사용하고 있지요. 그래서 남용이라고 볼 수 있습니다. 이러면 사람들이 알아보겠죠. 제가 θ (1)을 쓰면 이런 것들을 단순화 하는 것이고, 기본적으로 같은 것을 뜻을 나타냅니다. 
 
자 그러면 이 두 가지를 정렬해 봅시다. 어떻게 설명할 수 있을까요? 이것을 하는 시간, ⌈⌈n/2⌉의 T와 n-⌈n/2⌉의 T를 더해서 재귀적으로 설명할 수 있습니다. 사실 약간 복잡합니다. 그래서 우리는 정확하지는 않지만, 2T(n/2)라고 씁니다. 약간은 엉성한데, 금요일 설명시간에 이렇게 하는 것이 괜찮은지 알아보도록 하겠습니다. 
 
이것이 알고리즘에 정말 유용한 점입니다. 여러분이 철저하고 정확하면, 원하는 만큼 간단하게 할 수 있습니다.[웃음] 그렇지만, 이것이 어떻게 될지에 대해서는 걱정하지 않아도 됩니다. 큰 차이가 없기 때문입니다. 그 경우에 대해서는 앞으로 보게 될 것입니다. 그리고 마지막으로, 정렬된 두 리스트들을 합쳐야 합니다. 그리고 합병 서브 루틴(merge subroutine)을 이용한 것을 분석하면 θ (n)이 나오게 됩니다. 
 
합병 정렬(merge sort)의 성능에 대해 회귀(recurrence)를 쓸 수 있습니다. T(n)은 n이 1일 때, θ (1)이고, n이 1보다 클 때, 2T(n/2)+ θ (n)입니다. 스탭 1 을 해도, 스탭 1,2,3을 해도 모두 그렇습니다. 스탭 1을 하면, 다시 돌아가서 끝나게 되고, 그렇지 않으면, 돌아가지 않고, 스탭 2,3을 하게 될 것입니다. 그래서 이렇게 식을 쓸 수 있습니다. 제가 θ (n)+ θ (1)이라고 말했지만, θ (1)이 θ (n)보다는 작기 때문에 지워도 되고 그래서 결국 θ (n)이 됩니다. θ (1)이거나, 2T(n/2)+ θ (n)입니다. 일반적으로 θ (1)은 쓰지 않습니다. 
 
보통은 이것을 생략합니다. 회귀의 솔루션에 차이가 없다면, 보통은 생략합니다. 사실 수학적으로 사실은 아니지만, 알고리즘에서 일정한 크기의 입력(input)에서 어떤 프로그램을 실행시키면, 항상 일정한 시간을 얻게 됩니다. 그래서 이 값이 무엇인지는 신경 쓰지 않아도 됩니다. 반복의 점근적 솔루션에 어떠한 영향도 미치지 않습니다.  
 
이러한 회귀(recurrence)를 어떻게 풀 수 있을까요? T(n)을 T(n/2)의 관점에서 표현한 것이 책에 있고, 2번째 강의에서도 다루게 될 것입니다. 2번째 강의에서 해결해 보도록 하고요, 남은 시간 동안 할 것은 시각적으로 보여주는 것입니다. 다음시간에 어떤 것을 구체적으로 배우게 될지 말입니다. 이것은 재귀 트리(recursion tree)라고 불립니다. 
 
이것은 진짜 회귀에 쓰일 것인데, 거의 2T(n/2)와 같습니다. 이것이 발생하는 것을 사실적이고 명쾌하게 보여드리고 싶은데, T(n) = 2T(n/2)+cn이고, 여기서 상수 c는 0보다 큽니다. 기본적인 경우를 들어 회귀를 한번 보도록 하겠습니다. 
 
여기 있는 상수를 좀 더 분명하게 해보겠습니다. 재귀 트리(recursion tree)에서 우리가 하는 방법은 다음과 같습니다. 우선 식의 왼쪽 부분을 먼저 적어줍니다. 그리고 나서 같다(‘=’) 표시를 써주고, cn에 트리 처럼 두 개의 T(n/2) 자식을 추가해 줍니다. T(n/2), T(n/2)... 이것을 요약하면 T(n)을 얻게 됩니다. 그래서 T(n)=2T(n/2)+cn 식이 나오게 되는 것입니다. 여기 두 개의 T(n/2)과 cn이 있지요? 그리고 또 해보겠습니다. 여기 cn이 있고, 그 다음 2개의 cn/2가 있습니다. 그리고 각각의 cn/2에는 4개의 T(n/4)이 있습니다. 그리고 계속 해 나갑니다. ... 그러면 결국 이런 것이 나오게 되지요. 
 
 
단말 노드(leaf)에 도달 할 때까지 계속 해 나갑니다. 그리고 하나의 단말 노드는 기본적으로 T(1)입니다. 그리고 T(1)은 θ(1)이지요. 그러면 여기서 문제 드리겠습니다. 이 트리의 높이(height)는 무엇입니까? 네, log n. 사실 log n에 매우 가깝습니다. n에서 시작해서 n/2, n/4 그리고 그런 식으로 쭉 1까지 갑니다. 1까지 도달하는데, n이 나누어진 것들의 수는 log n이지요. 그래서 여기서 높이(hight)는 log n입니다. 좋습니다. 앞에 상수 c가 있어도 c는 상관 없습니다. 그러면, 이 트리에는 얼마나 많은 단말 노드들이 있습니까? 
 
이 트리에는 단말 노드(leaves)가 몇 개 있을까요? 네, 단말노드의 수는 n입니다. 간단한 가정을 통해서 생각해보면, n은 2의 거듭제곱이고, 정수입니다. 그러면 T(1)에 도달할 때, 정확하게 log n이 되지요. 그러면 n개의 단말 노드(leaves)가 생기고, 각 레벨(level)에서 1,2,4,8의 노드들이 만들어 집니다.  
 
우리가 수학을 했네요. 그렇죠? 자, 그러면 각 레벨에서 얼마나 많은 일을 하게 되는지 알아봅시다. 만약 이 트리의 모든 것을 합산하면 T(n)을 얻게 될 것입니다. 한번 계산해 보도록 하죠. 레벨 한 개씩 계산해 보겠습니다. 첫 번째 레벨에는 얼마가 될까요? cn입니다. 두 번째 레벨은 어떨까요? 역시 cn입니다. 세 번째도 cn입니다. 그러면 모두 합산하면 얼마가 될까요? θ (n)이 됩니다.  
 
반드시 cn일 필요는 없습니다. 가장 마지막의 경우에는 다른 상수를 가질 수도 있기 때문입니다. 사실은 θ (n)입니다. 그렇지만, 이 부분은 계속 cn이지요. 모든 것을 다 합해서 계산하면, cnlog n이 되고, 그것이 높이(hegiht)입니다. 그리고 + θ(n)이 됩니다. cnlog n이 θ(n)보다 높은 순서의 항이니까, 남기고, 상수 c를 제거하면 θ(nlog n)이 됩니다. θ(nlog n)은 점근적으로 θ(n^2)보다 빠릅니다. 그래서 합병 정렬(merge sort)은 입력의 크기가 클 때 삽입 정렬(insertion sort)보다 빠릅니다.  
 
합병 정렬(merge sort)는 더 빠른 알고리즘이 됩니다. 죄송합니다. 여기 칠판이 안 보이는 것을 신경 못썼네요. 잘 안보이면 크게 말해주세요. θ(nlog n)이 θ(n^2)보다 더 느리게 커집니다. 그래서 합병 정렬(merge sort)은 점근적으로 삽입 정렬(insertion sort)를 이기게 됩니다. 여러분이 삽입 정렬(insertion sort)을 슈퍼 컴퓨터에서 실행시켜도 입력이 많은 합병 정렬(merge sort)를 돌리는 PC가 훨씬 빠를 것입니다. 왜냐하면 일단 n이 커지면, n^2는 n log n 보다 훨씬 더 크기 때문입니다. 실제로 여기에서도 30보다 큰 입력 크기를 넣게 되면 합병 정렬(merge sort)이 이기는 경향이 있습니다.  
 
만약 30개의 원소들처럼 매우 적은 입력을 넣는다면, 삽입 정렬(insertion sort)은 완벽하게 사용하기에 좋을 것입니다. 그러나 합병 정렬(merge sort)는 여기에서 입력의 크기가 크지 않아도 삽입 정렬(insertion sort)보다 훨씬 더 빠릅니다. 실제로도 더 빠른 알고리즘인 것이지요. 그것이 오늘 꼭 알아두어야 할 점입니다. 알겠죠? 설명 과제 받는 것과 금요일에 꼭 와야 하는 것 잊지 말고요. 많은 것을 다루게 될 테니 꼭 참석해야 합니다. 그러면 다음 주 월요일에 보도록 합시다.  
 
 
 
 
* MIT OCW 강의들은 SNOW에 의해서 번역되고 있습니다. MIT대학, MIT대학의 교수진들 및 MIT OCW는 SNOW가 번역한 스크립트를 검토하거나 승인하는 일과는 관계가 없습니다. MIT대학 및 MIT OCW는 SNOW의 번역물에 관련한 보증은 없으며, 상품성에 대한 보증과 특수한 목적, 사용 또는 적용을 위한 적합성 보증 및 모든 다른 의무와 책임을 포함하되 그에 제한되지 않고, 모든 다른 명시적 또는 묵시적 보증을 대체하고 배제합니다. MIT OCW는 번역 오류에 대해 어떠한 책임도 없으며 번역의 부정확함에 따른 어떠한 오류나 결함은 전적으로 MIT OCW가 아닌 SNOW에게 책임이 있다는 것을 명시하는 바입니다. (These MIT OpenCourseWare course materials have been translated into Korean by SNOW. The MIT faculty authors, MIT, or MIT OpenCourseWare have not reviewed or approved these translations, and MIT and MIT OpenCourseWare makes no representations or warranties of any kind concerning the translated materials, express or implied, including, without limitation, warranties of merchantability, fitness for a particular purpose, non-infringement, or the absence of errors, whether or not discoverable. MIT OpenCourseWare bears no responsibility for any inaccuracies in translation. Any inaccuracies or other defects contained in this material, due to inaccuracies in language translation, are the sole responsibility of SNOW and not MIT OpenCourseWare.)
* 이 스크립트가 작성완료되었다면 스크립트 작성완료 요청하여 주십시오.
 
펼쳐보기

히스토리

프린트

We're going to get started. Handouts are the by the door if anybody didn't pick one up. My name is Charles Leiserson. I will be lecturing this course this term, Introduction to Algorithms, with Erik Demaine. In addition, this is an SMA course, a Singapore MIT Alliance course which will be run in Singapore by David Hsu. And so all the lectures will be videotaped and made available on the Web for the Singapore students, as well as for MIT students who choose to watch them on the Web. If you have an issue of not wanting to be on the videotape, you should sit in the back row. OK? Otherwise, you will be on it. 
 
There is a video recording policy, but it seems like they ran out. If anybody wants to see it, people, if they could just sort of pass them around maybe a little bit, once you're done reading it, or you can come up. I did secure one copy. Before we get into the content of the course, let's briefly go over the course information because there are some administrative things that we sort of have to do. 
 
As you can see, this term we have a big staff. Take a look at the handout here. Including this term six TAs, which is two more TAs than we normally get for this course. That means recitations will be particularly small. There is a World Wide Web page, and you should bookmark that and go there regularly because that is where everything will be distributed. Email. You should not be emailing directly to, even though we give you our email addresses, to the individual members of the staff. You should email us generally. And the reason is you will get much faster response. And also, for any communications, generally we like to monitor what the communications are so it's helpful to have emails coming to everybody on the course staff. As I mentioned, we will be doing distance learning this term. And so you can watch lectures online if you choose to do that. 
 
I would recommend, for people who have the opportunity to watch, to come live. It's better live. You get to interact. There's an intangible that comes with having it live. In fact, in addition to the videos, I meet weekly with the Singapore students so that they have a live session as well. Prerequisites. The prerequisites for this course are 6.042, which is Math for Computer Science, and 6.001. You basically need discrete mathematics and probability, as well as programming experience to take this course successfully. People do not have that background should not be in the class. We will be checking prerequisites. If you have any questions, please come to talk to us after class. 
 
Let's see. Lectures are here. For SMA students, they have the videotapes and they will also have a weekly meeting. Students must attend a one-hour recitation session each week. There will be new material presented in the recitation. Unlike the lectures, they will not be online. Unlike the lectures, there will not be lecture notes distributed for the recitations in general. And, yet, there will be material there that is directly on the exams. And so every term we say oh, when did you cover that? That was in recitation. You missed that one. So, recitations are mandatory. And, in particular, also let me just mention your recitation instructor is the one who assigns your final grade. So we have a grade meeting and keep everybody normal, but your recitation has the final say on your grade. 
 
Handouts. Handouts are available on the course Web page. We will not generally, except for this one, first handout, be bringing handouts to class. Textbook is this book, Introduction to Algorithms. MIT students can get it any of the local bookstores, including the MIT Coop. There is also a new online service that provides textbooks. You can also get a discount if you buy it at the MIT Press Bookstore. There is a coupon in the MIT Student Telephone Directory for a discount on MIT Press books. And you can use that to purchase this book at a discount. Course website. This is the course website. It links to the Stellar website, which is where, actually, everything will be kept. 
 
And SMA students have their own website. Some students find this course particularly challenges so we will have extra help. We will post weekly office hours on the course website for the TAs. And then as an experiment this term, we are going to offer homework labs for this class. What a homework lab is, is it's a place and a time you can go where other people in the course will go to do homework. 
 
And there will be typically two TAs who staff the lab. And so, as you're working on your homework, you can get help from the TAs if you need it. And it's generally a place, we're going to schedule those, and they will be on the course calendar for where it is and when it is that they will be held, but usually Sundays 2:00 to 4:00 pm, or else it will be some evening. I think the first one is an evening, right? 
 
Near to when the homework is due. Your best bet is try to do the homework in advance of the homework lab. But then, if you want extra help, if you want to talk over your solutions with people because as we will talk about problem sets you can solve in collaboration with other people in the class. In addition, there are several peer assistance programs. Also the office of Minority Education has an assistance program, and those usually get booked up pretty quickly. If you're interested in those, good idea to make an appointment to get there and get help soon. The homework labs, I hope a lot of people will try that out. We've never done this. I don't know of any other course. Do other people know of courses at MIT that have done this? 6.011 did it, OK. 
 
Good. And was it successful in that class? It never went, OK. Good. [LAUGHTER] We will see. If it's not paying off then we will just return to ordinary office hours for those TAs, but I think for some students that is a good opportunity. If you wish to be registered in this course, you must sign up on the course Web page. So, that is requirement one. It must be done today. You will find it difficult to pass the course if you are not in the class. And you should notify your TA if you decide to drop so that we can get you off and stop the mailings, stop the spam. And you should register today before 7:00 PM. 
 
And then we're going to email your recitation assignment to you before Noon tomorrow. And if you don't receive this information by Thursday Noon, please send us an email to the course staff generally, not to me individually, saying that you didn't receive your recitation assignment. And so if you haven't received it by Thursday Noon you want to. I think generally they are going to send them out tonight or at least by tomorrow morning. 
 
Yeah. OK. SMA students don't have to worry about this. Problem sets. We have nine problem sets that we project will be assigned during the semester. A couple things about problem sets. Homeworks won't generally be accepted, if you have extenuating circumstances you should make prior arrangements with your recitation instructor. In fact, almost all of the administrative stuff, you shouldn't come to me to ask and say can I hand in something late? You should be talking to your recitation instructor. 
 
You can read the other things about the form, but let me just mention that there are exercises that should be solved but not handed in as well to give you drill on the material. I highly recommend you doing the exercises. They both test your understanding of the material, and exercises have this way of finding themselves on quizzes. You're often asked to describe algorithms. And here is a little outline of what you can use to describe an algorithm. The grading policy is something that somehow I cover. And always every term there are at least a couple of students who pretend like I never showed them this. If you skip problems it has a nonlinear effect on your grade. Nonlinear, OK? 
 
If you don't skip any problems, no effect on your grade. If you skip one problem, a hundredth of a letter grade, we can handle that. But two problems it's a tenth. And, as you see, by the time you have skipped like five letter grades, it is already five problems. This is not problem sets, by the way. This is problems, OK? You're down a third of a letter grade. And if you don't do nine or more, so that's typically about three to four problem sets, you don't pass the class. I always have some students coming at the end of the year saying oh, I didn't do any of my problems. Can you just pass me because I did OK on the exams? Answer no, a very simple answer because we've said it upfront. So, the problem sets are an integral part of the course. Collaboration policy. 
 
This is extremely important so everybody pay attention. If you are asleep now wake up. Like that's going to wake anybody up, right? [LAUGHTER] The goal of homework. Professor Demaine and my philosophy is that the goal of homework is to help you learn the material. And one way of helping to learn is not to just be stuck and unable to solve something because then you're in no better shape when the exam roles around, which is where we're actually evaluating you. 
 
So, you're encouraged to collaborate. But there are some commonsense things about collaboration. If you go and you collaborate to the extent that all you're doing is getting the information from somebody else, you're not learning the material and you're not going to do well on the exams. In our experience, students who collaborate generally do better than students who work alone. But you owe it to yourself, if you're going to work in a study group, to be prepared for your study group meeting. And specifically you should spend a half an hour to 45 minutes on each problem before you go to group so you're up to speed and you've tried out your ideas. And you may have solutions to some, you may be stuck on some other ones, but at least you applied yourself to it. After 30 to 45 minutes, if you cannot get the problem, just sitting there and banging your head against it makes no sense. 
 
It's not a productive use of your time. And I know most of you have issues with having time on your hands, right? Like it's not there. So, don't go banging your head against problems that are too hard or where you don't understand what's going on or whatever. That's when the study group can help out. And, as I mentioned, we'll have homework labs which will give you an opportunity to go and do that and coordinate with other students rather than necessarily having to form your own group. 
 
And the TAs will be there. If your group is unable to solve the problem then talk to other groups or ask your recitation instruction. And, that's how you go about solving them. Writing up the problem sets, however, is your individual responsibility and should be done alone. You don't write up your problem solutions with other students, you write them up on your own. And you should on your problem sets, because this is an academic place, we understand that the source of academic information is very important, if you collaborated on solutions you should write a list of the collaborators. Say I worked with so and so on this solution. It does not affect your grade. It's just a question of being scholarly. 
 
It is a violation of this policy to submit a problem solution that you cannot orally explain to a member of the course staff. You say oh, well, my write-up is similar to that other person's. I didn't copy them. We may ask you to orally explain your solution. If you are unable, according to this policy, the presumption is that you cheated. So, do not write up stuff that you don't understand. You should be able to write up the stuff that you understand. Understand why you're putting down what you're putting down. If it isn't obvious, no collaboration whatsoever is permitted on exams. Exams is when we evaluate you. And now we're not interested in evaluating other people, we're interested in evaluating you. So, no collaboration on exams. We will have a take-home exam for the second quiz. 
 
You should look at the schedule. If there are problems with the schedule of that, we want to know early. And we will give you more details about the collaboration in the lecture on Monday, November 28th. Now, generally, the lectures here, they're mandatory and you have to know them, but I know that some people say gee, 9:30 is kind of early, especially on a Monday or whatever. It can be kind of early to get up. 
 
However, on Monday, November 28th, you fail the exam if you do not show up to lecture on time. That one day you must show up. Any questions about that? That one day you must show up here, even if you've been watching them on the Web. And generally, if you think you have transgressed, the best is to come to us to talk about it. We can usually work something out. It's when we find somebody has transgressed from a third-party or from obvious analyses that we do with homeworks, that's when things get messy. So, if you think, for some reason or other, oh, I may have done something wrong, please come and talk to us. We actually were students once, too, albeit many years ago. Any questions? So, this class has great material. 
 
Fabulous material. And it's really fun, but you do have to work hard. Let's talk content. This is the topic of the first part of the course. The first part of the course is focused on analysis. The second part of the course is focused on design. Before you can do design, you have to master a bunch of techniques for analyzing algorithms. And then you'll be in a position to design algorithms that you can analyze and that which are efficient. The analysis of algorithm is the theoretical study -- 
 
-- of computer program performance -- -- and resource usage. And a particular focus on performance. We're studying how to make things fast. In particular, computer programs. We also will discover and talk about other resources such as communication, such as memory, whether RAM memory or disk memory. There are other resources that we may care about, but predominantly we focus on performance. Because this is a course about performance, I like to put things in perspective a little bit by starting out and asking, in programming, what is more important than performance? 
 
If you're in an engineering situation and writing code, writing software, what's more important than performance? Correctness. Good. OK. What else? Simplicity can be. Very good. Yeah. Maintainability often much more important than performance. Cost. And what type of cost are you thinking? No, I mean cost of what? We're talking software here, right? What type of cost do you have in mind? 
 
There are some costs that are involved when programming like programmer time. So, programmer time is another thing also that might be. Stability. Robustness of the software. Does it break all the time? What else? Come on. We've got a bunch of engineers here. A lot of things. How about features? Features can be more important. Having a wider collection of features than your competitors. Functionality. Modularity. Is it designed in a way where you can make changes in a local part of the code and you don't have to make changes across the code in order to affect a simple change in the functionality? There is one big one which definitely, especially in the `90s, was like the big thing in computers. 
 
The big thing. Well, security actually. Good. I don't even have that one down. Security is excellent. That's actually been more in the 2000. Security has been far more important often than performance. Scalability has been important, although scalability, in some sense, is performance related. But, yes, scalability is good. What was the big breakthrough and why do people use Macintosh rather than Windows, those people who are of that religion? 
 
User-friendliness. Wow. If you look at the number of cycles of computers that went into user-friendliness in the `90s, it grew from almost nothing to where it's now the vast part of the computation goes into user-friendly. So, all those things are more important than performance. This is a course on performance. Then you can say OK, well, why do we bother and why study algorithms and performance if it's at the bottom of the heap? Almost always people would rather have these other things than performance. You go off and you say to somebody, would I rather have performance or more user-friendliness? 
 
It's almost always more important than performance. Why do we care then? Yeah? That wasn't user-friendly. Sometimes performance is correlated with user-friendliness, absolutely. Nothing is more frustrating than sitting there waiting, right? So, that's a good reason. What are some other reasons why? Sometimes they have real-time constraints so they don't actually work unless they perform adequately. Yeah? Hard to get, well, we don't usually quantify user-friendliness so I'm not sure, but I understand what you're saying. He said we don't get exponential performance improvements in user-friendliness. 
 
We often don't get that in performance either, by the way. [LAUGHTER] Sometimes we do, but that's good. There are several reasons that I think are important. Once is that often performance measures the line between the feasible and the infeasible. We have heard some of these things. For example, when there are real-time requirements, if it's not fast enough it's simply not functional. Or, if it uses too much memory it's simply not going to work for you. And, as a consequence, what you find is algorithms are on the cutting edge of entrepreneurship. If you're talking about just re-implementing stuff that people did ten years ago, performance isn't that important at some level. But, if you're talking about doing stuff that nobody has done before, one of the reasons often that they haven't done it is because it's too time-consuming. 
 
Things don't scale and so forth. So, that's one reason, is the feasible versus infeasible. Another thing is that algorithms give you a language for talking about program behavior, and that turns out to be a language that has been pervasive through computer science, is that the theoretical language is what gets adopted by all the practitioners because it's a clean way of thinking about things. A good way I think about performance, and the reason it's on the bottom of the heap, is sort of like performance is like money, it's like currency. You say what good does a stack of hundred dollar bills do for you? Would you rather have food or water or shelter or whatever? And you're willing to pay those hundred dollar bills, if you have hundred dollar bills, for that commodity. 
 
Even though water is far more important to your living. Well, similarly, performance is what you use to pay for user-friendliness. It's what you pay for security. And you hear people say, for example, that I want greater functionality, so people will program in Java, even though it's much slower than C, because they'll say it costs me maybe a factor of three or something in performance to program in Java. 
 
But Java is worth it because it's got all these object-oriented features and so forth, exception mechanisms and so on. And so people are willing to pay a factor of three in performance. So, that's why you want performance because you can use it to pay for these other things that you want. And that's why, in some sense, it's on the bottom of the heap, because it's the universal thing that you quantify. 
 
Do you want to spend a factor of two on this or spend a factor of three on security, et cetera? And, in addition, the lessons generalize to other resource measures like communication, like memory and so forth. And the last reason we study algorithm performance is it's tons of fun. Speed is always fun, right? Why do people drive fast cars, race horses, whatever? Rockets, et cetera, why do we do that? Because speed is fun. Ski. Who likes to ski? I love to ski. I like going fast on those skis. It's fun. Hockey, fast sports, right? We all like the fast sports. Not all of us, I mean. Some people say he's not talking to me. OK, let's move on. That's sort of a little bit of a notion as to why we study this, is that it does, in some sense, form a common basis for all these other things we care about. 
 
And so we want to understand how can we generate money for ourselves in computation? We're going to start out with a very simple problem. It's one of the oldest problems that has been studied in algorithms, is the problem of sorting. We're going to actually study this for several lectures because sorting contains many algorithmic techniques. The sorting problem is the following. We have a sequence a_1, a_2 up to a_n of numbers as input. And our output is a permutation of those numbers. 
 
A permutation is a rearrangement of the numbers. Every number appears exactly once in the rearrangement such that, I sometimes use a dollar sign to mean "such that," a_1 is less than or equal to a_2 prime. Such that they are monotonically increasing in size. Take a bunch of numbers, put them in order. Here's an algorithm to do it. It's called insertion sort. And we will write this algorithm in what we call pseudocode. It's sort of a programming language, except it's got English in there often. And it's just a shorthand for writing for being precise. 
 
So this sorts A from 1 to n. And here is the code for it. This is what we call pseudocode. And if you don't understand the pseudocode then you should ask questions about any of the notations. You will start to get used to it as we go on. One thing is that in the pseudocode we use indentation, where in most languages they have some kind of begin-end delimiters like curly braces or something in Java or C, for example. 
 
We just use indentation. The whole idea of the pseudocode is to try to get the algorithms as short as possible while still understanding what the individual steps are. In practice, there actually have been languages that use indentation as a means of showing the nesting of things. It's generally a bad idea, because if things go over one page to another, for example, you cannot tell what level of nesting it is. 
 
Whereas, with explicit braces it's much easier to tell. So, there are reasons why this is a bad notation if you were doing software engineering. But it's a good one for us because it just keeps things short and makes fewer things to write down. So, this is insertion sort. Let's try to figure out a little bit what this does. It basically takes an array A and at any point the thing to understand is, we're setting basically, we're running the outer loop from j is 2 to n, and the inner loop that starts at j minus 1 and then goes down until it's zero. 
 
Basically, if we look at any point in the algorithm, we essentially are looking at some element here j. A of j, the jth element. And what we do essentially is we pull a value out here that we call the key. And at this point the important thing to understand, and we'll talk more about this in recitation on Friday, is that there is an invariant that is being maintained by this loop each time through. 
 
And the invariant is that this part of the array is sorted. And the goal each time through the loop is to increase, is to add one to the length of the things that are sorted. And the way we do that is we pull out the key and we just copy values up like this. And keep copying up until we find the place where this key goes, and then we insert it in that place. And that's why it's called insertion sort. We just sort of move the things, copy the things up until we find where it goes, and then we put it into place. And now we have it from A from one to j is sorted, and now we can work on j plus one. 
 
Let's give an example of that. Imagine we are doing 8, 2, 4, 9, 3, 6. We start out with j equals 2. And we figure out that we want to insert it there. Now we have 2, 8, 4, 9, 3, 6. Then we look at the four and say oh, well, that goes over here. We get 2, 4, 8, 9, 3, 6 after the second iteration of the outer loop. Then we look at 9 and discover immediately it just goes right there. Very little work to do on that step. So, we have exactly the same output after that iteration. Then we look at the 3 and that's going to be inserted over there. 
 
2, 3, 4, 8, 9, 6. And finally we look at the 6 and that goes in there. 2, 3, 4, 6, 8, 9. And at that point we are done. Question? The array initially starts at one, yes. A[1...n], OK? So, this is the insertion sort algorithm. And it's the first algorithm that we're going to analyze. And we're going to pull out some tools that we have from our math background to help to analyze it. First of all, let's take a look at the issue of running time. 
 
The running time depends, of this algorithm depends on a lot of things. One thing it depends on is the input itself. For example, if the input is already sorted -- -- then insertion sort has very little work to do. Because every time through it's going to be like this case. It doesn't have to shuffle too many guys over because they're already in place. Whereas, in some sense, what's the worst case for insertion sort? If it is reverse sorted then it's going to have to do a lot of work because it's going to have to shuffle everything over on each step of the outer loop. 
 
In addition to the actual input it depends, of course, on the input size. Here, for example, we did six elements. It's going to take longer if we, for example, do six times ten to the ninth elements. If we were sorting a lot more stuff, it's going to take us a lot longer. Typically, the way we handle that is we are going to parameterize things in the input size. We are going to talk about time as a function of the size of things that we are sorting so we can look at what is the behavior of that. And the last thing I want to say about running time is generally we want upper bonds on the running time. 
 
We want to know that the time is no more than a certain amount. And the reason is because that represents a guarantee to the user. If I say it's not going to run, for example, if I tell you here's a program and it won't run more than three seconds, that gives you real information about how you could use it, for example, in a real-time setting. Whereas, if I said here's a program and it goes at least three seconds, you don't know if it's going to go for three years. It doesn't give you that much guarantee if you are a user of it. Generally we want upper bonds because it represents a guarantee to the user. 
 
There are different kinds of analyses that people do. The one we're mostly going to focus on is what's called worst-case analysis. And this is what we do usually where we define T of n to be the maximum time on any input of size n. So, it's the maximum input, the maximum it could possibly cost us on an input of size n. What that does is, if you look at the fact that sometimes the inputs are better and sometimes they're worse, we're looking at the worst case of those because that's the way we're going to be able to make a guarantee. 
 
It always does something rather than just sometimes does something. So, we're looking at the maximum. Notice that if I didn't have maximum then T(n) in some sense is a relation, not a function, because the time on an input of size n depends on which input of size n. I could have many different times, but by putting the maximum at it, it turns that relation into a function because there's only one maximum time that it will take. 
 
Sometimes we will talk about average case. Sometimes we will do this. Here T of n is then the expected time over all inputs of size n. It's the expected time. Now, if I talk about expected time, what else do I need to say here? What does that mean, expected time? I'm sorry. Raise your hand. Expected inputs. What does that mean, expected inputs? I need more math. What do I need by expected time here, math? You have to take the time of every input and then average them, OK. That's kind of what we mean by expected time. Good. Not quite. I mean, what you say is completely correct, except is not quite enough. 
 
Yeah? It's the time of every input times the probability that it will be that input. It's a way of taking a weighted average, exactly right. How do I know what the probability of every input is? How do I know what the probability a particular input occurs is in a given situation? I don't. I have to make an assumption. What's that assumption called? What kind of assumption do I have to meet? I need an assumption -- 
 
-- of the statistical distribution of inputs. Otherwise, expected time doesn't mean anything because I don't know what the probability of something is. In order to do probability, you need some assumptions and you've got to state those assumptions clearly. One of the most common assumptions is that all inputs are equally likely. That's called the uniform distribution. Every input of size n is equally likely, that kind of thing. But there are other ways that you could make that assumption, and they may not all be true. This is much more complicated, as you can see. Fortunately, all of you have a strong probability background. And so we will not have any trouble addressing these probabilistic issues of dealing with expectations and such. 
 
If you don't, time to go and say gee, maybe I should take that Probability class that is a prerequisite for this class. The last one I am going to mention is best-case analysis. And this I claim is bogus. Bogus. No good. Why is best-case analysis bogus? Yeah? The best-case probably doesn't ever happen. Actually, it's interesting because for the sorting problem, the most common things that get sorted are things that are already sorted interestingly, or at least almost sorted. For example, one of the most common things that are sorted is check numbers by banks. They tend to come in, in the same order that they are written. 
 
They're sorting things that are almost always sorted. I mean, it's good. When upper bond, not lower bound? Yeah, you want to make a guarantee. And so why is this not a guarantee? You're onto something there, but we need a little more precision here. How can I cheat? Yeah? Yeah, you can cheat. You cheat. You take any slow algorithm that you want and just check for some particular input, and if it's that input, then you say immediately yeah, OK, here is the answer. And then it's got a good best-case. 
 
But I didn't tell you anything about the vast majority of what is going on. So, you can cheat with a slow algorithm that works fast on some input. It doesn't really do much for you so we normally don't worry about that. Let's see. What is insertion sorts worst-case time? Now we get into some sort of funny issues. First of all, it sort of depends on the computer you're running on. Whose computer, right? Is it a big supercomputer or is it your wristwatch? They have different computational abilities. 
 
And when we compare algorithms, we compare them typically for relative speed. This is if you compared two algorithms on the same machine. You could argue, well, it doesn't really matter what the machine is because I will just look at their relative speed. But, of course, I may also be interested in absolute speed. Is one algorithm actually better no matter what machine it's run on? And so this kind of gets sort of confusing as to how I can talk about the worst-case time of an algorithm of a piece of software when I am not talking about the hardware because, clearly, if I had run on a faster machine, my algorithms are going to go faster. So, this is where you get the big idea of algorithms. 
 
Which is why algorithm is such a huge field, why it spawns companies like Google, like Akamai, like Amazon. Why algorithmic analysis, throughout the history of computing, has been such a huge success, is our ability to master and to be able to take what is apparently a really messy, complicated situation and reduce it to being able to do some mathematics. And that idea is called asymptotic analysis. 
 
And the basic idea of asymptotic analysis is to ignore machine-dependent constants -- -- and, instead of the actual running time, look at the growth of the running time. So, we don't look at the actual running time. We look at the growth. Let's see what we mean by that. This is a huge idea. It's not a hard idea, otherwise I wouldn't be able to teach it in the first lecture, but it's a huge idea. We are going to spend a couple of lectures understanding the implications of that and will basically be doing it throughout the term. 
 
And if you go on to be practicing engineers, you will be doing it all the time. In order to do that, we adopt some notations that are going to help us. In particular, we will adopt asymptotic notation. Most of you have seen some kind of asymptotic notation. Maybe a few of you haven't, but mostly you should have seen a little bit. The one we're going to be using in this class predominantly is theta notation. 
 
And theta notation is pretty easy notation to master because all you do is, from a formula, just drop low order terms and ignore leading constants. For example, if I have a formula like 3n^3 = 90n^2 - 5n + 6046, I say, well, what low-order terms do I drop? Well, n^3 is a bigger term n^2 than. I am going to drop all these terms and ignore the leading constant, so I say that's Theta(n^3). That's pretty easy. So, that's theta notation. Now, this is an engineering way of manipulating theta notation. There is actually a mathematical definition for this, which we are going to talk about next time, which is a definition in terms of sets of functions. And, you are going to be responsible, this is both a math and a computer science engineering class. 
 
Throughout the course you are going to be responsible both for mathematical rigor as if it were a math course and engineering commonsense because it's an engineering course. We are going to be doing both. This is the engineering way of understanding what you do, so you're responsible for being able to do these manipulations. You're also going to be responsible for understanding the mathematical definition of theta notion and of its related O notation and omega notation. 
 
If I take a look as n approached infinity, a Theta(n^2) algorithm always beats, eventually, a Theta(n^3) algorithm. As n gets bigger, it doesn't matter what these other terms were if I were describing the absolute precise behavior in terms of a formula. If I had a Theta(n^2) algorithm, it would always be faster for sufficiently large n than a Theta(n^3) algorithm. It wouldn't matter what those low-order terms were. It wouldn't matter what the leading constant was. This one will always be faster. 
 
Even if you ran the Theta(n^2) algorithm on a slow computer and the Theta(n^3) algorithm on a fast computer. The great thing about asymptotic notation is it satisfies our issue of being able to compare both relative and absolute speed, because we are able to do this no matter what the computer platform. On different platforms we may get different constants here, machine-dependent constants for the actual running time, but if I look at the growth as the size of the input gets larger, the asymptotics generally won't change. For example, I will just draw that as a picture. If I have n on this axis and T(n) on this axis. 
 
This may be, for example, a Theta(n^3) algorithm and this may be a Theta(n^2) algorithm. There is always going to be some point n_o where for everything larger the Theta(n^2) algorithm is going to be cheaper than the Theta(n^3) algorithm not matter how much advantage you give it at the beginning in terms of the speed of the computer you are running on. Now, from an engineering point of view, there are some issues we have to deal with because sometimes it could be that that n_o is so large that the computers aren't big enough to run the problem. That's why we, nevertheless, are interested in some of the slower algorithms, because some of the slower algorithms, even though they may not asymptotically be slower, I mean asymptotically they will be slower. 
 
They may still be faster on reasonable sizes of things. And so we have to both balance our mathematical understanding with our engineering commonsense in order to do good programming. So, just having done analysis of algorithms doesn't automatically make you a good programmer. You also need to learn how to program and use these tools in practice to understand when they are relevant and when they are not relevant. There is a saying. 
 
If you want to be a good program, you just program ever day for two years, you will be an excellent programmer. If you want to be a world-class programmer, you can program every day for ten years, or you can program every day for two years and take an algorithms class. Let's get back to what we were doing, which is analyzing insertion sort. We are going to look at the worse-case. Which, as we mentioned before, is when the input is reverse sorted. The biggest element comes first and the smallest last because now every time you do the insertion you've got to shuffle everything over. 
 
You can write down the running time by looking at the nesting of loops. What we do is we sum up. What we assume is that every operation, every elemental operation is going to take some constant amount of time. But we don't have to worry about what that constant is because we're going to be doing asymptotic analysis. As I say, the beautify of the method is that it causes all these things that are real distinctions to sort of vanish. 
 
We sort of look at them from 30,000 feet rather than from three millimeters or something. Each of these operations is going to sort of be a basic operation. One way to think about this, in terms of counting operations, is counting memory references. How many times do you actually access some variable? That's another way of sort of thinking about this model. When we do that, well, we're going to go through this loop, j is going from 2 to n, and then we're going to add up the work that we do within the loop. We can sort of write that in math as summation of j equals 2 to n. And then what is the work that is going on in this loop? Well, the work that is going on in this loop varies, but in the worst case how many operations are going on here for each value of j? 
 
For a given value of j, how much work goes on in this loop? Can somebody tell me? Asymptotically. It's j times some constant, so it's theta j. So, there is theta j work going on here because this loop starts out with i being j minus 1, and then it's doing just a constant amount of stuff for each step of the value of i, and i is running from j minus one down to zero. So, we can say that is theta j work that is going on. Do people follow that? 
 
OK. And now we have a formula we can evaluate. What is the evaluation? If I want to simplify this formula, what is that equal to? Sorry. In the back there. Yeah. OK. That's just Theta(n^2), good. Because when you're saying is the sum of consecutive numbers, you mean what? What's the mathematic term we have for that so we can communicate? You've got to know these things so you can communicate. It's called what type of sequence? It's actually a series, but that's OK. What type of series is this called? Arithmetic series, good. Wow, we've got some sharp people who can communicate. 
 
This is an arithmetic series. You're basically summing 1 + 2 + 3 + 4, some constants in there, but basically it's 1 + 2 + 3 + 4 + 5 + 6 up to n. That's Theta(n^2). If you don't know this math, there is a chapter in the book, or you could have taken the prerequisite. Erythematic series. People have this vague recollection. Oh, yeah. Good. Now, you have to learn these manipulations. We will talk about a bit next time, but you have to learn your theta manipulations for what works with theta. And you have to be very careful because theta is a weak notation. A strong notation is something like Leibniz notation from calculus where the chain rule is just canceling two things. 
 
It's just fabulous that you can cancel in the chain rule. And Leibniz notation just expresses that so directly you can manipulate. Theta notation is not like that. If you think it is like that you are in trouble. You really have to think of what is going on under the theta notation. And it is more of a descriptive notation than it is a manipulative notation. There are manipulations you can do with it, but unless you understand what is really going on under the theta notation you will find yourself in trouble. 
 
And next time we will talk a little bit more about theta notation. Is insertion sort fast? Well, it turns out for small n it is moderately fast. But it is not at all for large n. So, I am going to give you an algorithm that is faster. It's called merge sort. I wonder if I should leave insertion sort up. Why not. I am going to write on this later, so if you are taking notes, leave some space on the left. Here is merge sort of an array A from 1 up to n. 
 
And it is basically three steps. If n equals 1 we are done. Sorting one element, it is already sorted. All right. Recursive algorithm. Otherwise, what we do is we recursively sort A from 1 up to the ceiling of n over 2. And the array A of the ceiling of n over 2 plus one up to n. So, we sort two halves of the input. And then, three, we take those two lists that we have done and we merge them. 
 
And, to do that, we use a merge subroutine which I will show you. The key subroutine here is merge, and it works like this. I have two lists. Let's say one of them is 20. I am doing this in reverse order. I have sorted this like this. And then I sort another one. I don't know why I do it this order, but anyway. Here is my other list. I have my two lists that I have sorted. So, this is A[1] to A[|n/2|] and A[|n/2|+1] to A[n] for the way it will be called in this program. And now to merge these two, what I want to do is produce a sorted list out of both of them. 
 
What I do is first observe where is the smallest element of any two lists that are already sorted? It's in one of two places, the head of the first list or the head of the second list. I look at those two elements and say which one is smaller? This one is smaller. Then what I do is output into my output array the smaller of the two. And I cross it off. And now where is the next smallest element? And the answer is it's going to be the head of one of these two lists. Then I cross out this guy and put him here and circle this one. Now I look at these two guys. This one is smaller so I output that and circle that one. Now I look at these two guys, output 9. So, every step here is some fixed number of operations that is independent of the size of the arrays at each step. 
 
Each individual step is just me looking at two elements and picking out the smallest and advancing some pointers into the array so that I know where the current head of that list is. And so, therefore, the time is order n on n total elements. The time to actually go through this and merge two lists is order n. We sometimes call this linear time because it's not quadratic or whatever. It is proportional to n, proportional to the input size. It's linear time. I go through and just do this simple operation, just working up these lists, and in the end I have done essentially n operations, order n operations each of which cost constant time. 
 
That's a total of order n time. Everybody with me? OK. So, this is a recursive program. We can actually now write what is called a recurrence for this program. The way we do that is say let's let the time to sort n elements to be T(n). Then how long does it take to do step one? That's just constant time. We just check to see if n is 1, and if it is we return. That's independent of the size of anything that we are doing. It just takes a certain number of machine instructions on whatever machine and we say it is constant time. We call that theta one. This is actually a little bit of an abuse if you get into it. 
 
And the reason is because typically in order to say it you need to say what it is growing with. Nevertheless, we use this as an abuse of the notation just to mean it is a constant. So, that's an abuse just so people know. But it simplifies things if I can just write theta one. And it basically means the same thing. Now we recursively sort these two things. How can I describe that? The time to do this, I can describe recursively as T of ceiling of n over 2 plus T of n minus ceiling of n over 2. That is actually kind of messy, so what we will do is just be sloppy and write 2T(n/2). So, this is just us being sloppy. 
 
And we will see on Friday in recitation that it is OK to be sloppy. That's the great thing about algorithms. As long as you are rigorous and precise, you can be as sloppy as you want. [LAUGHTER] This is sloppy because I didn't worry about what was going on, because it turns out it doesn't make any difference. And we are going to actually see that that is the case. And, finally, I have to merge the two sorted lists which have a total of n elements. And we just analyze that using the merge subroutine. And that takes us to theta n time. 
 
That allows us now to write a recurrence for the performance of merge sort. Which is to say that T of n is equal to theta 1 if n equals 1 and 2T of n over 2 plus theta of n if n is bigger than 1. Because either I am doing step one or I am doing all steps one, two and three. Here I am doing step one and I return and I am done. Or else I am doing step one, I don't return, and then I also do steps two and three. So, I add those together. I could say theta n plus theta 1, but theta n plus theta 1 is just theta n because theta 1 is a lower order term than theta n and I can throw it away. It is either theta 1 or it is 2T of n over 2 plus theta n. Now, typically we won't be writing this. 
 
Usually we omit this. If it makes no difference to the solution of the recurrence, we will usually omit constant base cases. In algorithms, it's not true generally in mathematics, but in algorithms if you are running something on a constant size input it takes constant time always. So, we don't worry about what this value is. And it turns out it has no real impact on the asymptotic solution of the recurrence. 
 
How do we solve a recurrence like this? I now have T of n expressed in terms of T of n over 2. That's in the book and it is also in Lecture 2. We are going to do Lecture 2 to solve that, but in the meantime what I am going to do is give you a visual way of understanding what this costs, which is one of the techniques we will elaborate on next time. It is called a recursion tree technique. And I will use it for the actual recurrence that is almost the same 2T(n/2), but I am going to actually explicitly, because I want you to see where it occurs, plus some constant times n where c is a constant greater than zero. So, we are going to look at this recurrence with a base case of order one. 
 
I am just making the constant in here, the upper bound on the constant be explicit rather than implicit. And the way you do a recursion tree is the following. You start out by writing down the left-hand side of the recurrence. And then what you do is you say well, that is equal to, and now let's write it as a tree. I do c of n work plus now I am going to have to do work on each of my two children. 
 
T of n over 2 and T of n over 2. If I sum up what is in here, I get this because that is what the recurrence says, T(n)=2T(n/2)+cn. I have 2T(n/2)+cn. Then I do it again. I have cn here. I now have here cn/2. And here is cn/2. And each of these now has a T(n/4). And these each have a T(n/4). And this has a T(n/4). And I keep doing that, the dangerous dot, dot, dots. And, if I keep doing that, I end up with it looking like this. 
 
And I keep going down until I get to a leaf. And a leaf, I have essentially a T(1). That is T(1). And so the first question I ask here is, what is the height of this tree? Yeah. It's log n. It's actually very close to exactly log n because I am starting out at the top with n and then I go to n/2 and n/4 and all the way down until I get to 1. The number of halvings of n until I get to 1 is log n so the height here is log n. It's OK if it is constant times log n. It doesn't matter. How many leaves are in this tree, by the way? 
 
How many leaves does this tree have? Yeah. The number of leaves, once again, is actually pretty close. It's actually n. If you took it all the way down. Let's make some simplifying assumption. n is a perfect power of 2, so it is an integer power of 2. Then this is exactly log n to get down to T(1). And then there are exactly n leaves, because the number of leaves here, the number of nodes at this level is 1, 2, 4, 8. 
 
And if I go down height h, I have 2 to the h leaves, 2 to the log n, that is just n. We are doing math here, right? Now let's figure out how much work, if I look at adding up everything in this tree I am going to get T(n), so let's add that up. Well, let's add it up level by level. How much do we have in the first level? Just cn. If I add up the second level, how much do I have? cn. How about if I add up the third level? cn. How about if I add up all the leaves? Theta n. 
 
It is not necessarily cn because the boundary case may have a different constant. It is actually theta n, but cn all the way here. If I add up the total amount, that is equal to cn times log n, because that's the height, that is how many cn's I have here, plus theta n. And this is a higher order term than this, so this goes away, get rid of the constants, that is equal to theta(n lg n). And theta(n lg n) is asymptotically faster than theta(n^2). So, merge sort, on a large enough input size, is going to beat insertion sort. 
 
Merge sort is going to be a faster algorithm. Sorry, you guys, I didn't realize you couldn't see over there. You should speak up if you cannot see. So, this is a faster algorithm because theta(n lg n) grows more slowly than theta(n^2). And merge sort asymptotically beats insertion sort. Even if you ran insertion sort on a supercomputer, somebody running on a PC with merge sort for sufficient large input will clobber them because actually n^2 is way bigger than n log n once you get the n's to be large. And, in practice, merge sort tends to win here for n bigger than, say, 30 or so. 
 
If you have a very small input like 30 elements, insertion sort is a perfectly decent sort to use. But merge sort is going to be a lot faster even for something that is only a few dozen elements. It is going to actually be a faster algorithm. That's sort of the lessons, OK? Remember that to get your recitation assignments and attend recitation on Friday. Because we are going to be going through a bunch of the things that I have left on the table here. And see you next Monday.
펼쳐보기

작성참여하기  자막참여 히스토리 자막다운로드 

펼쳐보기
강의자 챨스 E. 라이서손
제공자 MIT OCW
원본출처 http://www.youtube.com/watch?v=JPyuH4qXLZ0
등록자 쪽지
태그 알고리즘,  정수론,  heap,  hassing
저작권
총 23강
  • 1강 : 알고리즘 분석

    1강 : 알고리즘 분석

    2강 : 점근 표기법과 되풀이

    2강 : 점근 표기법과 되풀이

    3강 : 분할 해결법

    3강 : 분할 해결법

    4강 : 퀵 정렬

    4강 : 퀵 정렬

    5강 : 정렬 하한계와 선형 시간 정렬

    5강 : 정렬 하한계와 선형 시간 정렬

    6강 : 순서 통계량

    6강 : 순서 통계량

  • 7강 : 해싱 I

    7강 : 해싱 I

    8강 : 해싱 II

    8강 : 해싱 II

    9강 : 임의 구축 이진 검색 트리

    9강 : 임의 구축 이진 검색 트리

    10강 : 균형 검색 트리

    10강 : 균형 검색 트리

    11강 : 데이터 구조 증대

    11강 : 데이터 구조 증대

    12강 : 스킵 리스트

    12강 : 스킵 리스트

  • 13강 : 상각 분석

    13강 : 상각 분석

    14강 : 경쟁력 분석

    14강 : 경쟁력 분석

    15강 : 동적 프로그래밍

    15강 : 동적 프로그래밍

    16강 : 탐욕 알고리즘과 그래프

    16강 : 탐욕 알고리즘과 그래프

    17강 : 최단 경로 I

    17강 : 최단 경로 I

    18강 : 최단 경로 II

    18강 : 최단 경로 II

  • 19강 : 최단 경로 III

    19강 : 최단 경로 III

    20강 : 심화 학습

    20강 : 심화 학습

    21강 : 심화 학습(계속)

    21강 : 심화 학습(계속)

    22강 : 심화 학습(계속)

    22강 : 심화 학습(계속)

    23강 : 심화 학습(계속)

    23강 : 심화 학습(계속)

강의 댓글 [ 4 ]

댓글 폼
       
( 0 / 800byte )
17분 부터 보시기 바랍니다.
[2014/03/20 22:31.39]
컴퓨터로 인터넷 서핑을 한다거나 영화를 감상한다거나 등등 이러한 것들은 좋아했지만 컴퓨터의 알고리즘과 같은 이론적인 분야에 대해서는 관심도 없었고 배운다고 해도 큰 흥미를 느끼지 못했었습니다. 그러나 대학에 들어오면서 컴퓨터 과학과 관련된 교양 과목을 수강하게 되므로써 이전까지 제가 컴퓨터 이론은 재미가 없다라고 생각했던 것이 편견이라는 것을 깨달았습니다. 이 강의를 통해, 그리고 찰스 라이저슨 교수님의 명쾌한 설명을 통해, 컴퓨터 과학에 대해 조금이나마 더 알게 된 것 같아서 좋은 것 같습니다. 물론, 저 설명들이 이해가 가지 않는 부분들이 있지마는 그래도 컴퓨터 이론에 대한 두려움만은 어느 정도 해소되는 데에 많은 도움이 된 것 같습니다.^^
[2012/04/30 13:48.49]
저번 학기에 컴퓨터 수학 강의를 수강했는데, 오일러 패스나 크로스컬 알고리즘, 버블 소트 알고리즘 등 여러 알고리즘에 대하여 배울 수 있었습니다. 프로그래밍을 할 때 다양한 알고리즘들을 알고있다면 보다 효율적이고 체계적인 프로그램을 만들 수 있고, 그것은 그 프로그램의 성능은 향상시키겠지요. 이 강의에서 더욱 많은 알고리즘들을 배울 수 있었습니다.
[2011/08/15 23:34.07]
강의내용질문 아.. 영어 잘하고 싶네요. 누군가 해석 해주실 분 않계신가요?
[2010/02/24 12:14.51]
처음페이지이전페이지1다음페이지마지막페이지
관련 동영상 강의
컴퓨터과학 II: 프로그래밍 추상화

컴퓨터과학 II: 프로그래밍 추상화

응용과학 / 컴퓨터 과학
스탠포드대학
컴퓨터과학과 프로그래밍 입문 (8): 복잡도

컴퓨터과학과 프로그래밍 입문 (8): 복잡도

응용과학 / 컴퓨터 과학
MIT OCW 한글스크립트 영문스크립트

[컴퓨터과학과 프로그래밍 입문 : 8 강]

컴퓨터과학과 프로그래밍 입문 (10): 함수 분할 정복

컴퓨터과학과 프로그래밍 입문 (10): 함수 분할 정복

응용과학 / 컴퓨터 과학
MIT OCW 한글스크립트 영문스크립트

[컴퓨터과학과 프로그래밍 입문 : 10 강]

CS50 / 0주차: 수요일

CS50 / 0주차: 수요일

응용과학 / 컴퓨터 과학
하버드대학 영문스크립트

[컴퓨터 과학 개론 (CS50) : 1 강]

CS50 / 0주차: 금요일

CS50 / 0주차: 금요일

응용과학 / 컴퓨터 과학
하버드대학

[컴퓨터 과학 개론 (CS50) : 2 강]

Sitemap