Time complexity & Birthday problem with sorting

Time Complexity Problem

이 문제는 아래 코드를 보고 시간 복잡도를 구하는 문제이다. 이 문제는 while문의 i와 j 형태를 보고 전반적인 시간 복잡도를 구할 수 있다.

 

34)

What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is, n = 2k for some positive integer k. 

 

i = n ;

while ( i >= 1) { → log2 n

    j = i ;

        while ( j <= n) { → log2 n

            < body o f the while loop>

             //Needs ( 1 )

             j = 2 * j; → 안쪽 while문에서는 j에 2를 곱해주기 때문에 while문 반복 횟수가 2배 줄어든다.

        }

    i = floor(i /2) ; → 바깥쪽 while문에서는 i값이 1/2씩 줄기에, 마찬가지로 while문 반복 횟수가 2배 줄어든다.

}

 

위의 코드 설명처럼 (안쪽, 바깥쪽) while문 모두 i와 j의 값 변화 때문에 (안쪽, 바깥쪽) 반복횟수가 log2 n이 된다.

따라서, 시간 복잡도는 T(n) = (log2 n)^2 = O((log2 n)^2)

 

Birthday problem with Sorting

저번에 살펴봤던 Birthday problem은 STL에 내장된 sort 함수를 이용해 문제를 풀었다. 이번에는 Selection sort 정렬 방식을 이용해 문제를 풀어보고자 한다.

 

Approach 1. Selection Sort (선택 정렬)

Step 1. Verbal Description

Approach. Selection Sort 함수로 생일을 정렬시킨 후 동일한 생일을 가진 학생의 쌍을 구해보자

전체 학생 생일 정보를 읽어 선택 정렬을 이용해 오름차순으로 정렬한 후 동일한 생일을 가진 학생들끼리 묶는다. 여기서 선택 정렬은 배열 안에서 최솟값이나 최댓값을 찾고, 남은 정렬 부분의 앞에 있는 데이터와 swap하는 것이 선택 정렬의 핵심이다.

 

Step 2. Inductive Proof

n개의 수를 담은 배열 ss에서 하나의 수를 선택해 선택 정렬을 하면, 재귀 호출로 인해 시간 복잡도는 ss(n) = ss(n-1) + Θ(1)이 된다. ss(n) = cn이라고 치환했을 때, 시간 복잡도 식은 cn = c(n-1) + Θ(1)가 된다. 여기서 Θ(1) = c가 되면, 증명이 성공했다고 볼 수 있다. 실제로 식을 풀었을 때도 Θ(1) = c가 나오므로, 위의 가정은 성립한다. 

 

그러면 전체 선택 정렬 알고리즘에 대한 시간 복잡도를 계산해보면, T(n) = T(n-1) + Θ(n)이라고 가정했을 때, Θ(n)은 n에 관한 식으로 나와야 한다. 마찬가지로, T(n) = cn^2이라고 하면 시간 복잡도 식은 cn^2 = c(n-1)^2 + Θ(n)이 된다. 여기서 Θ(n) = 2cn - c가 된다. 

 

따라서, 선택 정렬 함수의 시간 복잡도는 O(n^2)이므로 (2cn - c)^2의 형태이다.

 

Step 3. Efficiency

시간 복잡도

: Selection Sort 함수 → O(n^2)

: 정렬된 데이터 비교 → O(n) 

 

최종 효율성은 O(n^2)으로 효율적이지 않은 편이다.

 

<슈도 코드>

cnt = 96명 중 동일한 생일을 가진 쌍의 개수
n = 총 사람 수
birthday = 각 사람들의 생일
p = 96명 중 두 사람이 동일한 생일을 가질 확률
min = selection sort를 진행할 때 swap에 이용할 최소 생일 날짜 변수

    vector <int> v; // 모든 사람들의 생일 날짜 저장
    vector <int> contain; // 동일한 생일 날짜 저장
    
    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    // selection sort 구현
    for (int i = 0; i < n; i++) {

        min = i;

        for (int j = i+1; j < n; j++) {
            if (v[min] > v[j]) {
                min = j;
            }
        }

        if (v[min] < v[i]) {
            int tmp = v[i];
            v[i] = v[min];
            v[min] = tmp;
        }
    }

    for (int i = 1; i < n; i++) {

        if (v[i - 1] == v[i]) {
            cnt += 1;
            contain.push_back(v[i - 1]);
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }
    }

    fp.close();

 

<전체 코드>

// selection sort
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> v;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    // selection sort 구현
    for (int i = 0; i < n; i++) {

        min = i;

        for (int j = i+1; j < n; j++) {
            if (v[min] > v[j]) {
                min = j;
            }
        }

        if (v[min] < v[i]) {
            int tmp = v[i];
            v[i] = v[min];
            v[min] = tmp;
        }
    }

    for (int i = 1; i < n; i++) {

        if (v[i - 1] == v[i]) {
            cnt += 1;
            contain.push_back(v[i - 1]);
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }
    }

    fp.close();

}