11.3 정렬의 하한 여기까지 정렬에 대한 논의를 다시 요약하면, 크기가 n인 입력 시퀀스에 대해 O(nlogn)인 최악의 경우 또는 예상 실행 시간을 가진 몇 가지 방법을 설명했다. 이러한 방법에는 이 장에서 설명하는 병합 정렬과 퀵 정렬뿐만 아니라 8.3.5절에서 설명하는 힙 정렬도 포함된다. 그렇다면 자연스럽게 할 수 있는 질문은 O(nlogn) 시간보다 더 빠른 정렬이 가능한가 하는 것이다. 이 절에서는 정렬 알고리즘이 사용하는 계산 기본값이 두 요소를 비교하는 것이라면, 비교 기반 정렬이 실행 시간에 Ω(nlogn) 최악의 경우 하한값을 갖는다는 것을 보여준다. (섹션 4.2.3의 표기법 Ω(·)을 참조하라.) 비교 기반 정렬의 주요 비용에 초점을 맞추기 위해, 정렬 알고리즘이 수행하는 비교만 ..

10.1 객체 지향 프로그래밍이란? 10.1.1 클래스란? 클래스(class): 개체 유형을 정의하기 위해 "함께 묶"되는 인스턴스 변수 및 메서드 집합을 지정한다. ex) String Class name: 'John Smith' street: '8 Crown Street' city/state: 'Baltimore, Maryland' zip_code: '21284' name.isdigit() ➝ False address.isdigit() ➝ False city_state.isdigit() ➝ False zip_code.isdigit() ➝ True 10.1.2 객체 지향 프로그래밍의 세 가지 기본 속성 캡슐화(encapsulation), 상속(heritance), 다형성(polymorphism)은 객체 ..