시간복잡도 표기법

Big - O 표기법 기본개념

알고리즘의 사용량을 예측하는 방법이다.
시간복잡도의 핵심요소는 반복문이다.
알고리즘 최악의 실행 시간을 표기(최악의 상황에서도 보장하는 알고리즘의 수행 속도를 의미
성능 보장을 의미하기때문에 가장 많이 사용하는 표기법이다.

문제 24262번 O(1) - constant time

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

위의 코드를 실행할때 반복되는 횟수(수행횟수)와 다항식으로 나타내엇을때 최고차항의 차수를 출력하여라

코드 및 풀이

public class Main {
    public static void main(String[] args) {
        System.out.println(1);
        System.out.println(0);
    }
}

위 함수는 배열과 n을 받아서 특정 값만 리턴하는 코드이다.
이 함수는 n이 10 100 1억이 되더라도 상관없이 항상 같은 시간이 걸리게 된다.
그래서 O(1) constant time의 시간복잡도를 가지게 된다.
수행횟수는 단 1번 시간복잡도는 차수가 없기때문에 0이다.

문제 24263번 O(n) - linear time

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

위의 코드를 실행할때 반복되는 횟수(수행횟수)와 다항식으로 나타내엇을때 최고차항의 차수를 출력하여라

코드 및 풀이

public class Main {
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        System.out.println(n);
        //n^1
        System.out.println(1);
    }
}

위 함수는 n값을 받아서 1부터 n까지 횟수를 '반복'하는 알고리즘을 가지고 있는 것으로 보인다.
n이 늘어나면 늘어날수록 반복을 늘어나게 되므로 O(n) - linear time라고 한다.
수행횟수는 n번 시행하게 되고 시간복잡도는 n의 1차그래프를 가지고 우상향하기 때문에 1이다.

문제 O(n^2) - quadratic time

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

위의 코드를 실행할때 반복되는 횟수(수행횟수)와 다항식으로 나타내엇을때 최고차항의 차수를 출력하여라

코드 및 풀이

public class Main {
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long n =Long.parseLong(br.readLine());

        System.out.println(n * n);
        //n^2
        System.out.println(2);
    }
}

위 함수는 n값을 받아 n번씩 도는 이중반복문의 형태를 가지고 잇다.
n이 늘어나면 늘어날수록 O(n) * O(n)만큼 시간복잡도를 즉 O(n^2)의 복잡도를 가지게 된다.
그래서 수행회수는 n*n번 시간복잡도는 n의 2제곱이기 때문에 2이다.