[ALGORITHM] 04. O(n)

O(n)은 선형 시간 복잡도를 나타내며, 입력 크기에 선형으로 비례하여 실행 시간이 증가하는 알고리즘을 의미한다.

즉, 입력 크기가 n일 때, 실행 시간은 n에 정비례한다.

 

예시 1

 

int summation(int data[], int n) {

    int sum = 0;
    
    for (int i = 0; i < n; i++) { //for 반복문 내부 문장이 n번 실행 : O(n)
    
        sum = sum + data[i];
    }
    
    return sum;
}

 

예시 2

 

int variance(int data[], int n) {

    int sum = 0;
    
    for (int i = 0; i < n; i++) { //for 반복문 1
    
        sum = sum + data[i];
    }

    double mean = static_cast<double>(sum) / n;
    double var = 0.0;
    
    for (int i = 0; i < n; i++) { //for 반복문 2
    
        var += (data[i] - mean) * (data[i] - mean);
    } // for 반복문 내부 문장이 2n번 실행 : O(n)

    return (var / n);
}

 

예시 3

 

int find(int data[], int n, int target) {

    for (int i = 0; i < n; i++) {
    
        if (data[i] == target) { //최선의 경우 for반복문 안의 비교 연산이 1회
           return i;             //최악의 경우 n번 실행 : O(n)
        }
    }
    
    return -1;
}

 

예시 4

 

int sum(int n) {
    
    if (n == 1) {
    
       return 1;
    }
    
    return n + sum(n - 1); //재귀 함수가 n번 호출되고, 함수 내부에 단일 연산만 있음 : O(n)
}