[INA240] Data Structures and Practice 01. Basic Concepts [INA240] Data Structures and Practice Youn-Hee Han http://link.kut.ac.kr

1. Pseudo code Algorithm Five elements of Algorithm a finite set of instruction that accomplishes a particular task Five elements of Algorithm Input: zero or more quantities Output: at least one quantity Definiteness: clear and unambiguous instructions Finiteness: for all cases, algorithm terminates after finite step Different from program Effectiveness: basic and feasible instructions Data Structure

1. Pseudo code Algorithm Data Algorithm 절차 [요리 재료] 스펀지케이크(20×20cm) 1개, 크림치즈 200g, 달걀 푼 물 2개 분량, 설탕 3큰술, 레몬즙·바닐라에센스 1큰술씩, 딸기시럽(딸기 500g, 설탕 1½ 컵, 레몬즙 1작은술), 딸기 1개, 플레인 요구르트 2큰술 Data [요리법] ① 케이크 틀의 가장자리에 필름을 돌린 다음 스펀지케이크를 놓는다. ② 볼에 크림치즈를 넣고 거품기로 젓다가 달걀 푼 물과 설탕 3큰술을 세번에 나누어 넣으면서 크림 상태로 만든다. ③ ②에 레몬즙과 바닐라에센스를 넣고 살짝 저은 다음 ①에 붓는다. 이것을 180℃의 오븐에 넣고 20분 정도 굽는다. ④ 냄비에 슬라이스한 딸기와 설탕 1½ 컵을 넣고 끓이다가 약한 불에서 눌어붙지 않도록 저으면서 거품을 걷어낸다. 되직해지면 레몬즙을 넣고 차게 식힌다. ⑤ 접시에 치즈케이크를 한 조각 담고 ④의 시럽을 뿌린 다음 플레인 요구르트와 딸기를 얹어낸다 . Algorithm 절차 Data Structure

1. Pseudo code Pseudo code Why pseudo code? an English-like representation of the algorithm logic. Consists only of executable statements in a specific order Not actually executed on computers Helps us “think out” a program before writing it Why pseudo code? Let us concentrate on problem solving Language independent Easy to convert into a program Data Structure

1. Pseudo code Elements of Pseudo Code Header Statement Numbers Algorithm name, List of parameters, Purpose Conditions (Pre-condition, Post-condition) Return with condition Statement Numbers 1,2,3,… 1.1, 1.2,… Variables Use intelligent data names Do not use single-character names "studuentCount" instead of "count“, "numOfStu" instead of "noStu“ Statements Any algorithm can be written using three kinds of constructs Sequence, Selection, Loop Data Structure

1. Pseudo code Pseudo Code Example - 1 An algorithm to read a file and print a report read a line from file pageNumber Data Structure

1. Pseudo code Pseudo Code Example - 2 An algorithm to print deviation from mean for series Data Structure

2. Abstract Data Type Bad Programming Style Good Programming Style Spaghetti code Non-structured and linear program in which the logic flow wound through the program. Good Programming Style Modular Programming Programs are organized in functions Structured Programming Data Structure

2. Abstract Data Type Data and Data Type Data Atomic data: single piece of data (undividable) int, char, float, … Composite data Phone number (XXX-XXXX-XXXX) Data type = a set of data + operations Data Structure

2. Abstract Data Type Data Structure Data Structure Data structure aggregation of atomic/composite data (type) into a set with defined relationships Structures means a set of associations (relationships or rules) involving the combined elements Data structures can be nested A data structure can consist of other data structure Data Structure A combination of elements in which each is either a data type or another data structure A set of associations or relationships (structure) involving the combined elements Data Structure

2. Abstract Data Type Data Structure Examples Why associations (or relationship)? Data (Type) A set of associations Data Structure

2. Abstract Data Type Data Structure 컴퓨터에 의한 문제 해결 과정 바로 이 부분에 자료구조가 활용된다. - 즉, 주어진 문제를 가장 효율적으로 풀기 위하여 처리대상을 어떻게 조직적으로 관리할 것인가를 배우는 것이 이 과목의 목적이다. - 가끔은 자료를 효율적으로 조직화하는 것만으로도 주어진 문제 자체를 해결할 수도 있다. Data Structure

2. Abstract Data Type Abstraction (in general) 추상화와 구체화 추상화 – “무엇(what)인가?”를 논리적으로 정의 구체화 – “어떻게(how) 할 것인가?”를 실제적으로 표현 the process or result of generalization by reducing the information content of a concept or an observable phenomenon, typically in order to retain only information which is relevant for a particular purpose. (from http://en.wikipedia.org/wiki/Abstraction) Data Structure

2. Abstract Data Type Data Abstraction (in Computer Science) Separation of a data type’s logical properties from its implementation Abstract Data Type (ADT) a specification of a set of data and the set of operations that can be performed on the data Data and operations are specified independently of any particular implementation. LOGICAL PROPERTIES IMPLEMENTATION What are the possible values? How can this be done in C++? What operations will be needed? How can data types be used? Data Structure

2. Abstract Data Type ADT의 특징 ADT에 대한 구현 (Implementation) 프로그램의 대상이 되는 사물이나 현상을 추상적으로 정의 추상적 정의이기 때문에 세부 구현내용을 몰라도 사용가능 추상화를 통하여 복잡도를 줄이는 것 추상 자료형의 사용자 입장에서는 구체적으로 어떤 방법으로 그 작업이 이루어지는 지는 알바가 아니고 알고 싶지도 않다. ADT에 대한 구현 (Implementation) 자료 구조 (Data Structure) a way of storing data in a computer so that it can be used efficiently 자료 구조와 ADT와의 관계 추상 자료형이 자료에 대한 논리적인 성질들을 설명하는 반면에 자료 구조는 자료에 대한 구체적인 구현을 의미한다. Data Structure

2. Abstract Data Type 얼음 제조기의 추상화 ADT IceDispenser       : GetMeChilledWater( );   냉수 주시요.       : GetMeCrushedIce( );     부순 얼음 주시요.       : GetMeCubeIce( );        각진 얼음 주시요. Data Structure

2. Abstract Data Type 얼음 제조기의 구체화 자료구조의 역할 작업을 수행하기 위한 구체적인 방법을 기술 구현 관점 (Implementation View) 작업을 수행하기 위한 구체적인 방법을 기술 자료구조의 역할 물, 모터, 버튼 등의 데이터 집합에 대한 구현 데이터는 그 데이터를 가공할 작업을 전제로 설계되어야 함 작업이 가장 효율적으로 수행될 수 있도록 조직화된 데이터 집합 구조체(Structure)로 가져갈지 아니면 배열(Array)로 가져갈지….. 하지만, ADT의 사용자 입장에서는 자료구조에는 관심이 없음 IceDispenser - Data       : Water, Motor, Button   물, 모터, 버튼 - Operation        : GetMeChilledWater( ) {   …… //냉수 주시요의 구체적 구현         }               : GetMeCrushedIce( ) {              …… // 부순 얼음 주시요의 구체적 구현 }        : GetMeCubeIce( ) {                 …… // 각진 얼음 주시요의 구체적 구현 } Data Structure

2. Abstract Data Type Let’s think ‘Library’ ADT 어떠한 자료구조와 알고리즘을 사용할 것인가? Data Structure

2. Abstract Data Type Viewing a library from 3 different levels Application (or user) level Library of Congress, or Baltimore County Public Library. Logical (or ADT) level domain is a collection of books; operations include: check book out, check book in, pay fine, reserve a book. Implementation level representation of the structure to hold the “books”, and the coding for operations. Data Structure

2. Abstract Data Type 추상 자료형과 C 인터페이스 파일과 구현파일의 분리 헤더 파일의 예 헤더 파일 헤더 파일(.h): 인터페이스 파일, 소스 파일(.c): 구현 파일 헤더 파일의 예 typedef struct { int Water;    물의 양             int Motor;    모터 회전수     int Button;   버튼 1, 2, 3 } materialType; void GetMeChilledWater( );     냉수 주시요 void GetMeCrushedIce( );      부순 얼음 주시요 void GetMeCubeIce( );          각진 얼음 주시요 헤더 파일 함수 프로토타입(Prototype)만 보여 줌 블랙 박스 (구현을 볼 수 없음 - 정보의 은닉을 약간 실현함) 계약서(Specification) 역할 작업의 정의를 자세하고 정확하게 기술 Data Structure

2. Abstract Data Type Abstract Data Type 정리 Abstract data type: data type organized by Specifications of objects Requirements/properties of objects Specifications of operations on the objects Description of what the function does. Names, arguments, result of each functions  “what a data type can do.” Abstract data type does not include Representation of objects Implementation of operations  “How it is done is hidden.” Data Structure

2. Abstract Data Type List 를 어떻게 구현할 것인가? 위 네 가지 예제는 Data Structure의 예 ADT 관점에서의 List는 위 네 가지 구현 방법에 대한 신경을 쓰지 않음 Data Structure

3. Model for an Abstract Data Type ADT model Data structures Operations (public and private functions) Encapsulation of data and operations Data Structure

3. Model for an Abstract Data Type ADT model ADT operations: interface of ADT Operation name and parameters are accessible from ADT Private function are hidden from outside of ADT ADT data structure Implementation is hidden All data about the structure are maintained only inside the ADT Data Structure

< Array A of size n > 4. ADT Implementations Two basic structures to implement ADT’s Array: mapping from index to element Linked list: (logically) ordered collection of data, in which each element contains location of the next element A[0] A[1] A[2] A[n-1] … < Array A of size n > Data Structure

self-referential structure 4. ADT Implementations Linear lists 구조체 선언 예 struct Node { int data; struct Node *next; }; self-referential structure Data Structure

4. ADT Implementations How to make a code to generate the following linked list? 1. Declare nodes struct Node a, b; a.data = 10; b.data = 20; 2. Linking nodes a.link = &b; b.link = NULL; a b data (10) link data (20) link a b data (10) link data (20) link (NULL) Data Structure

4. ADT Implementations Non-linear lists 구조체 선언 예 1 구조체 선언 예 2 struct Node { struct Node *l_link; int data; struct Node *r_link; }; 구조체 선언 예 2 struct Node { int data; struct Node *next[3]; }; Data Structure

6. Algorithm Efficiency (p.28~) Given a set of algorithms for the same problem, how to compare their efficiency (or complexity)? Function without loop nor recursion Execution time < # of instructions composing the function> Function containing loop or recursion Execution time is a function of input size N Ex) finding a particular student from a enrollment General format of algorithm efficiency Efficiency of an algorithm: f(n) n: size of input Data Structure

6. Algorithm Efficiency 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency) 공간적 효율성은 얼마나 많은 메모리 공간을 요하는가를 말한다. 시간적 효율성은 얼마나 많은 시간을 요하는가를 말한다. 효율성을 뒤집어 표현하면 복잡도(Complexity)가 된다. 복잡도가 높을수록 효율성은 저하된다. 일반적으로 시간적 효율성이 공간적 효율성보다 더욱 강조가 됨 시간적 복잡도 (Time Complexity) 분석 하드웨어 환경에 따라 처리시간이 달라진다. 부동소수 처리 프로세서 존재유무, 나눗셈 가속기능 유무 입출력 장비의 성능, 공유여부 소프트웨어 환경에 따라 처리시간이 달라진다. 프로그램 언어의 종류, 운영체제, 컴파일러의 종류 운영체제에 현재 어느 정도의 load가 걸리고 있는가? 이러한 환경적 차이로 인해 분석이 어렵다. 그래서, 실행환경과 무관하게 개략적으로 분석하고 입력 데이터의 수에 따르는 명령어 수행 개수로 분석한다. Data Structure

6. Algorithm Efficiency 문자가 총 N 개로 구성된 스트링의 각 문자들을 출력하는 함수 복잡도를 구하는 예 할당 한번 시간을 a, 비교 한번 시간을 b, 출력 한번 시간을 c라고 가정 정확한 총 실행시간은 a(N+1) + b(N+1) + cN = (a+b+c)N + (a+b) a, b, c 계수 값은 실행환경에 따라 달라진다. 일반적으로… 단순히 “실행시간이 N에 비례”하는 알고리즘이라고 말함. 실행환경에 따른 계수는 무시해버린다. void display(char* string) {          i = 0; while (string[i]!= ‘/0’) {   printf("%c", string[i]);       i++;   } } Data Structure

6. Algorithm Efficiency Linear Loops Execution time is proportional to n for(i = 0; i < n; i++){ // application code } for(i = 0; i < n; i += 2){  f(n) = n  f(n) = n/2 Data Structure

6. Algorithm Efficiency Logarithmic Loops Execution time is proportional to logd(n) Multiply for(i = 1; i <= n; i *= 2){ // application code } Division for(i = n; i >= 1; i /= 2){ Termination conditions Multiply: 2Iteration > n Division: n / 2Iteration < 1  f(n) = log2(n)

6. Algorithm Efficiency Nested Loops Basic formula Linear logarithm Total iterations = outer loop iteration * inner loop iteration Linear logarithm for(i = 0; i < n; i++){ // outer loop: n iterations for(j = 0; j < n; j *= 2){ // inner loop: log2(n) iterations // application code }  f(n) = n log2(n)

6. Algorithm Efficiency Nested Loops Quadratic Dependent quadratic for(i = 0; i < n; i++){ // outer loop: n iterations for(j = 0; j < n; j++){ // inner loop: n iterations // application code }  Total iterations: f(n) = n2 Dependent quadratic for(j = 0; j < i; j++){ // inner loop: (n+1)/2 iterations  f(n) = n(n+1)/2 If n=10, the number of iteration of the inner loop: 1+2+3+...+10 = 55 55/10 = 11/2 = (10+1)/2=5.5

6. Algorithm Efficiency Comparison of Algorithms Given two algorithms whose complexities are f1(n) and f2(n) respectively, then … Is the order of magnitude important? n vs. n2, n2 vs. n3, … Is the constant factor important? 0.5n vs. 10n, n2 vs. 2n2, n vs. log n, … More difficult cases 5n vs. n2 100n vs. 0.001n2 100000000n vs. 0.000000001n2

6. Algorithm Efficiency 동일 문제 해결을 위한 알고리즘 A와 B를 생각해 보자 아래와 같은 A와 B 의 Complexity라면 A가 당연히 효율적 A는 ‘N에 비례’ B는 ‘N2에 비례’ 그러나, 좀 더 정확히 표현하여 아래와 같은 A와 B 라면? A는 1500N B는 2N2 실행환경에 따른 변수인 계수 값을 무시하지 않는다면 어느 정도 작은 N에 대하여 B가 더 효율적이다. 그렇다면 어떤 방법을 이용해야 하나? 답: Asymptotic Complexity Asymptotic Complexity (점근적 복잡도) 일반적으로 시간적 효율을 말할 때에는 N이 무한히 큰 경우로 국한 즉, ‘입력 데이터의 크기 N이 무한대로 갈 때 알고리즘의 실행시간이 어디에 접근하는가?’ Data Structure

6. Algorithm Efficiency Order vs. Constant Factor Comparing c1n with c2n2 (c1 and c2 are constants) Regardless of c1 and c2, there exists a break even point. Consequently … Order of magnitudes are important Constant factors are negligible 즉, N이 무한대로 갈 때를 기준으로 평가한다. 입력 데이터가 최악일 때 알고리즘이 보이는 효율을 기준으로 한다. c2n2 c1n break even point

6. Algorithm Efficiency Big-O Notation Roughly, O(f(n)) represents “order of” f(n) 1, 3, 100, …  O(f(n))=O(1) Constant complexity (independent from size of input) n, 0.5n, 10n, 1000000n,…  O(f(n))=O(n) Linear complexity n2, 0.5n2, 10n2, 1000000n2,…  O(f(n))=O(n2) Quadratic complexity Big-O 구하는 법에 관한 요약 주어진 함수의 가장 높은 차수의 항만 고려 데이터 크기 n의 함수로 표시하되 계수를 무시한다.

6. Algorithm Efficiency Growth of Function Values Ordering of complexities O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn) Plot of function values

6. Algorithm Efficiency Growth of Function Values If n is sufficiently large, the only important is the order of complexity. Ex) If n is sufficiently large, 100n + 1 < 0.00001n2

6. Algorithm Efficiency Quadratic Time Algorithm (제곱시간 알고리즘) 2 ((N-1)-2+1) N  O(N2) 실행시간이 데이터 개수의 제곱에 비례하는 알고리즘 for i = 1 to N    for  j = 2 to (N-1)      do { Read A[i, j];           Write A[i, j];       } Data Structure

6. Algorithm Efficiency Linear Time Algorithm (선형시간 알고리즘) (N-19001)⋅(MAX - 1)⋅2 = O(N) Constant Time Algorithm (상수시간 알고리즘) 두 번 실행 2 = 2N0 = O(N0) = O(1) 데이터 수 N에 무관하게 상수 번 수행되는 알고리즘 #define MAX 9000000 for i = 1000 to N-20000     for  j = 2 to MAX         do {             Read A[i, j];              Write A[i, j];           } x = 20; printf("%d", x); Data Structure

6. Algorithm Efficiency Exponential Time Algorithm (지수시간 알고리즘) O(aN) 사실상 컴퓨터로 실행하기 불가능할 정도의 많은 시간을 요하는 알고리즘 Logarithmic Time Algorithm (로그 시간 알고리즘) O(logN)으로서 O(N)보다 매우 빠른 알고리즘 로그함수의 밑수(Base)는 아무렇게나 표시 logbN = logN / logb = (1/logb)⋅logN . 빅 오 기호에서 계수는 무시 O(logbN) = O(logN) 기타사항 – 일반적으로 log2N을 lgN으로 표시 Data Structure

6. Algorithm Efficiency if statement가 있을 때의 효율 측정 최악의 경우에 대해서 평가: O(N2) 여러 부분로 나눌 수 있는 알고리즘인 경우 첫 부분 – O(N2), 두번째 부분 – O(N), 세번째 부분 – O(N3) O(N2 + N + N3) = O(N3) 가장 속도가 느린 부분이 전체적인 효율을 좌우하는 Dominant Factor가 됨 if (x = = 1) { for i = 1 to N       for  j = 2 to (N-1)           do {           Read A[i, j];               Write A[i, j];           } } else { x = 20;   printf("%d", x); } Data Structure

6. Algorithm Efficiency Two square matrices of the same size. Size ‘n’ is the number of columns or rows in a matrix Addition of two Square Matrices (p.35) Complexity: O(n2) Multiplication of Square Matrices (p.36~37) Complexity: O(n3) Data Structure

Perspectives on DATA Data Structure