[자료구조 - C언어] 자료구조 제19강: 시간복잡도 분석 예(1)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. Stack - push and pop

1-1. 배열로 구현한 경우

void push(Stack s, Item i){
    if(is_full(s))
        //스택에 저장된 데이터 개수를 n이라고 하면 reallocate 함수의 시간 복잡도는 O(n)
        reallocate(s); 
	
    //reallocate를 제외한 나머지 부분의 시간 복잡도는 O(1)
    s->top ++;
    s->contents[s->top] = i;
}

• reallocate를 제외한 나머지 연산은 스택 안의 데이터의 개수와 무관하기 때문에 → O(1)의 시간 복잡도
• 일반적으로 함수의 시간 복잡도에서 reallocate는 제외 ~ 애초에 스택의 크기를 크게 잡으면 되기 때문

void pop(Stack s){
    if(is_empty(s))
        terminate("Error in pop: stack is empty.");
    s->top--;
    return s->contents[s->top + 1];
}

• pop() 함수의 시간 복잡도는 O(1)이다.

1-2. 연결 리스트로 구현한 경우

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(= add_first)와 pop(= remove_first)는 스택 데이터의 개수와 무관 → O(1)의 시간 복잡도

 

2. Queue - enqueue and dequeue

• 맨 앞의 데이터를 삭제하거나 맨 뒤에 새로운 데이터를 추가하는 함수이기 때문에 큐의 길이와 무관
• 배열로 구현한 경우 역시 reallocate를 제외하면 enqueue와 dequeue 모두 O(1)의 시간 복잡도
• 연결 리스트로 구현한 경우 역시 enqueue와 dequeue 모두 O(1)의 시간 복잡도

 

3. 정렬된 리스트(ordered list)에 삽입하기

3-1. 배열

• 정렬된 리스트에 들어갈 위치를 찾고, 그 뒤의 데이터들은 한 칸씩 뒤로 shift
• 최악의 경우(= 새로 추가되는 데이터가 전체 데이터중 제일 작은 경우) 시간 복잡도는 O(n)이다.
• 개선 방법
  • 이진 검색을 하면 삽입할 위치를 찾는 시간을 O(logn)으로 줄일 수 있지만
    • 결국 shift하는데 O(n) 시간을 소요해서 전체적인 시간 복잡도는 O(n)
  • 앞에서부터 순차적으로 비교하면서 들어갈 위치를 찾기는 그렇게 좋지 않다
    • 삽입 위치를 찾기 위해 보다 작은 값도 봐야 하고, 뒤에 데이터도 shift 해야 하기 때문에
    • 결국 데이터 전체를 보아야 한다.
  • 뒤에서부터 검사하면서 삽입하려는 값 보다 크면 shift 하기
    • 작은 값들은 볼 필요 없기 때문에 가장 나은 방법

//뒤에서부터 검사하면서 삽입하려는 값 보다 크면 shift하기
void insert_to_ordered_array(int n, int data[], int item){
	//reallocate는 제외
	int i= n-1;
	for(; i>=0 && data[i]>item; i--)
		data[i+1] = data[i];
	data[i+1] = item;
}

3-2. 연결 리스트

• 연결 리스트는 이진 검색을 할 수 없다.
• 단방향 연결 리스트는 뒤에서부터 검사를 할 수 없다.
• 남은 한 가지 방법인 첫 번째부터 자기 자신보다 큰 수가 나올 때까지 비교하고, 그 앞에 위치해야 하는데
  • 단뱡향 연결 리스트는 노드의 앞에 삽입할 수 없기 때문에
  • q, p를 이용해서 add_after(q);

//함수에서 head가 지역변수라 head를 수정하면 함수 밖에서 변화가 적용되지 않기 때문에
//첫 번째 노드의 주소를 리턴
Node *insert_to_order_linked_list(Node *head, int item){
    Node *new_node = (Ndoe *)malloc(sizeof(Node));
    new_node->data = item;
    new_node->next = NULL;
	
    //최악의 경우 while문을 n번 반복해야 하기 때문에 O(n)의 시간 복잡도를 갖는다.
    Node *p = head, *q = NULL;
    while(p!=NULL && p->data < item){
        q = p;
        p = p->next;
    }
	
    //첫 번째 값이 이미 item 보다 커졌다: add_first
    if(q==NULL){
        new_node->next = head;
        head = new_node;    /head 노드 수정
    }
    else{    //add_after
        new_node->next = p;
        q->next = new_node;
    }
    return head;
}

• 최악의 경우(= 삽입하려는 데이터가 최댓값이라면) whlie문을 n번 반복해야 하기 때문에 → 최악의 경우 O(n)의 시간 복잡도
• head가 전역 변수 일 때
  • **head 를 매개변수로 받거나
  • head값을 리턴

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://youtu.be/U2jolV4ZitA