chap01_time_complexity.key

Size: px

Start display at page:

Download "chap01_time_complexity.key"

희진 순
6 years ago
Views:

1 1 :

2 (resource),,, 2

3 (time complexity),,, (worst-case analysis) (average-case analysis) 3

4 (Asymptotic) n growth rate Θ-, Ο- ( ) 4

5 : n data, n/2. int sample( int data[], int n ) { int k = n/2 ; return data[k] ; n. O(1). 5

6 : n data,. int sum(int data[], int n) { int sum = 0 ; for (int i = 0; i < n; i++) sum = sum + data[i]; return sum;, n. n n, n. O(n). 6

7 : data target. int search(int n, int data[], int target) { for (int i=0; i<n; i++) { if (data[i] == target) return i; return -1;, n. O(n). 7

8 Quadratic x. bool is_distinct( int n, int x[] ) { for (int i=0; i<n-1; i++) for (int j=i+1; j<n; j++) if (x[i]==x[j]) return false; return true;, n(n-1)/2. n(n-1)/2. O(n 2 ). 8

9 ? for (i=1; i<n; i*=2) { // Do something? 9

10 10

11 f(n) 2 O(g(n)) if there exist constant c>0 and n 0 0 such that for all n n 0 we have f(n) apple cg(n) f(n) = 32n n 2 32 f(n) 2 O(n 2 ) but also f(n) 2 O(n 3 ) and O(n 2 log n) 11

12 f(n) 2 (g(n)) if there exist constant c>0 and n 0 0 such that for all n n 0 we have f(n) cg(n). f(n) = 32n n 2 32 f(n) 2 (n 2 ) but also f(n) 2 (n) and (n log n) 12

13 :Θ- f(n) 2 (g(n)) if there exist constants c 1 > 0,c 2 > 0, and n 0 0 such that for all n n 0 we have 0 apple c 1 g(n) apple f(n) apple c 2 g(n). f(n) 2 (g(n)) if f(n) 2 O(g(n)) and f(n) 2 (g(n)) f(n) = 32n n 2 32 f(n) 2 (n 2 ) but f(n) 62 (n 3 ),f(n) 62 (n) 13

14 f(n) =O(g(n)) f(n) 2 O(g(n)) k 0 O(n k ) f(n) =c k n k + c k 1 n k c 1 n + c 0 = O(n k ) p q O(n max{p,q ) If g(n) =O(n p ) and h(n) =O(n q ), then f(n) =g(n)+h(n) =O(n max(p,q) ) 14

15 A B A = O(B)? A = (B)? log k n n k p n n c n n sin n 2 n 2 n/2 n log c c log n log(n!) log(n n ) 15

16 16 Common Growth Rate

17 17 Common Growth Rate

18 18 Common Growth Rate

19 19

20 20

21 (Binary Search). target Dustin Caryn Debbie Dustin Elliot Jacquie Jonathon Rich first = 0 middle = 3 last = 6 21

22 (Binary Search). target Dustin Caryn Debbie Dustin Elliot Jacquie Jonathon Rich first = 0 last = 2 middle = 1 22

23 (Binary Search). target Dustin Caryn Debbie Dustin Elliot Jacquie Jonathon Rich first= middle = last = 2 23

24 data n. int binarysearch(int n, char *data[], char *target) { int begin = 0, end = n-1; while(begin <= end) { int middle = (begin + end)/2; int result = strcmp(data[middle], target); if (result == 0) return middle; else if (result < 0) begin = middle+1; else end = middle-1; return -1;. O(log2n). 24

25 ? (middle) O(1). O(n) O(log2n).. 25

26 (bubble sort) void bubblesort(int data[], int n) { for ( int i=n-1; i>0; i--) { for ( int j=0; j<i; j++ ) { if (data[j] > data[j+1]) { int tmp = data[j]; data[j] = data[j+1]; data[j+1] = tmp;? 26

27 (Insertion sort) void insertion_sort(int n, int data[]) { for ( int i=1; i<n; i++) { int tmp = data[i]; int j = i-1; while (j>=0 && data[j]>data[i]) { data[j+1] = data[j]; j ; data[j+1] = tmp; data[i] 를 data[0] ~ data[i-1] i i i i? 27

28 (quicksort) O(n 2 ), O(nlog2n) O(nlog2n) (merge sort) (heap sort)? 28

29 Code Review 29

30 push and pop: void push(stack s, Item i) { if (is_full(s)) reallocate(s); s->top++; s->contents[s->top] = i; Item pop(stack s) { if (is_empty(s)) terminate("error in pop: stack is empty. ); s->top -; return s->contents[s->top+1]; n reallocate O(n). reallocate O(1). pop() O(1). 30

31 push and pop: void push(stack s, Item i) { struct node *new_node = malloc(sizeof(struct node)); if (new_node == NULL) terminate("error in push: stack is full."); new_node->data = i; new_node->next = s->top; s->top = new_node; Item pop(stack s) { struct node *old_top; Item i; if (is_empty(s)) terminate("error in pop: stack is empty."); old_top = s->top; i = old_top->data; s->top = old_top->next; free(old_top); return i; push pop O(1). 31

32 enqueue and dequeue reallocate enqueue dequeue O(1). enqueue dequeue O(1). 32

33 (ordered list) : void insert_to_ordered_array(int n, int data[], int item) { int i = n-1; for (; i>=0 && data[i]>item; i--) data[i+1] = data[i]; data[i+1] = item; O(n). 33

34 (ordered list) : Node *insert_to_ordered_linked_list(node *head, int item) { Node *new_node = (Node *)malloc(sizeof(node)); new_node->data = item; new_node->next = NULL; Node *p = head, *q=null; while (p!=null && p->data < item) { q = p; p = p->next; if (q==null) { new_node->next = head; head = new_node; else { new_node->next = p; q->next = new_node; return head; O(n)... 34

35 a b A B m n C. c void merge_sorted_arrays(int m, int a[], int n, int b[], int c[]) { for (int i=0; i<m; i++) a c c[i] = a[i]; for (int j=0; j<n; j++) b c insert. insert_to_ordered_array(m+j, c, b[j]); O(mn). 35

36 a b c void merge_sorted_arrays_linear(int m, int a[], int n, int b[], int c[]) { int i=0, j=0, k=0; while (i<m && j<n) { if (a[i] <= b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; while(i<m) c[k++] = a[i++]; while(j<n) c[k++] = b[j++]; O(m+n). 36

37 Node *merge_two_ordered_list(node *first, Node *second) { /* insert nodes of the second list into the first list */ Node *p = second; Node *q = first; while (p!=null) { Node *the_node = p; p = p->next; first = insert_to_ordered_list(first); return first; O(mn). 37

38 2 Node *merge_two_ordered_lists2(node *first, Node *second) { Node *head = NULL, *tail = NULL; Node *tmp; while (first!= NULL && second!= NULL) { if (first->data <= second->data) { tmp = first; first = first->next; else { tmp = second; second = second->next; first tmp->next = NULL; if (tail == NULL) { head = tail = tmp; else { tail->next = tmp; tail = tmp; second head tail 38

39 2 first NULL if (first!= NULL) tail->next = first; else if (second!= NULL) tail->next = second; return head; second head tail O(m+n). 39

40 3 Node *merge_two_ordered_list3(node *first, Node *second) { /* insert nodes of second into first */ Node *p = second; Node *q = first, *pre_q = NULL; while (p!=null) { Node *the_node = p; p = p->next; while(q!=null && q->data < the_node->data) { pre_q = q; q = q->next; if (pre_q == NULL) { /* add p at the front */ the_node->next = first; first = the_node; else { /* add after pre_q */ the_node->next = q; pre_q->next = the_node; pre_q = the_node; return first; O(m+n). 40

41 Node *inverse_list(node *head) { if (head == NULL head->next == NULL) return head; Node *p = head; Node *q = NULL; /* before p */ Node *r = p->next; /* next to p */ while (p!= NULL) { p->next = q; q = p; p = r; if (r!=null) r = r->next; return q; O(n). 41

42 Node *remove_all_divisible(node *head, int divisor) { Node *p = head; Node *q = NULL, *deleted = NULL; while(p!=null) { if (p->data%divisor == 0) { if (q==null) head = p->next; else q->next = p->next; deleted = p; p = p->next; free(deleted); else { q = p; p = p->next; return head; O(n). 42

43 int maze() { Stack s = create(); Position cur; cur.x = 0; cur.y = 0; int init_dir = 0; /* */ while(1) { maze[cur.x][cur.y] = VISITED; /* visited */ if (cur.x == n-1 && cur.y == n-1) { break; bool forwarded = false; for (int dir = init_dir; dir<4; dir++) { if (movable(cur, dir)) { push(s, dir); cur = move_to(cur, dir); forwarded = true; init_dir = 0; break; if (!forwarded) { maze[cur.x][cur.y] = BACKTRACKED; /* backtracked */ if (is_empty(s)) break; int d = pop(s); cur = move_to(cur, (d+2)%4); init_dir = d+1; 2 4. O(n 2 ). 43

44 Queue queue = create_queue(); Position cur; cur.x = 0; cur.y = 0; enqueue(queue, cur); maze[0][0] = -1; bool found = false; while(!is_empty(queue)) { Position cur = dequeue(queue); for (int dir=0; dir<4; dir++) { if (movable(cur, dir)) { Position p = move_to(cur, dir); maze[p.x][p.y] = maze[cur.x][cur.y] - 1; if (p.x == n-1 && p.y == n-1) { printf("found the path.\n"); found = true; break; enqueue(queue, p); 2. O(n 2 ). 44

5.스택(강의자료).key

5.스택(강의자료).key CHP 5: https://www.youtube.com/watch?v=ns-r91557ds ? (stack): (LIFO:Last-In First-Out):. D C B C B C B C B (element) C (top) B (bottom) (DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=.