[백준] 알고리즘 복잡도

같은 결과를 내는 알고리즘에도 효율성의 차이가 생긴다. 알고리즘 수행 시작부터 결과 도출까지 걸리는 시간이 짧고, 컴퓨터 자원을 적게 사용하는 효율적인 알고리즘을 짜는 것이 중요하다.

알고리즘을 평가할 때에는 시간복잡도와 공간복잡도를 사용한다

• 시간 복잡도(Time Complexity) : 알고리즘의 수행시간을 평가
• 공간 복잡도(Space Comlexity) : 알고리즘 수행에 필요한 메모리 양을 평가

 

점근적 표기법 - 시간복잡도를 나타내는 데에 사용

• Big-O 표기법 : 최악의 경우
• Big-θ 표기법 : 평균의 경우
• Big-Ω 표기법 : 최선의 경우

평균인 세타 표기법을 사용하면 좋겠지만 평가하기가 까다롭다. 그래서 최악의 경우인 빅오를 사용해서 성능을 측정한다.

 

 

Big O 표기법

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

O(1)

시간복잡도가 가장 낮은 상수 시간 복잡도이다. 어떤 알고리즘이 n의 크기에 관계없이 실행시간이 일정한 경우를 뜻한다.

해시테이블 알고리즘이 이 경우에 속한다.

O(log_2n)

최악의 경우에도 입력값 n이 증가하는 속도보다 수행시간이 천천히 증가하는 알고리즘의 성능이다.

이진탐색 알고리즘의 시간복잡도이다.

O(n)

입력값 n 만큼의 수행 시간을 요구하는 성능이다. 입력값 n이 증가하는 속도만큼 수행 시간도 같은 속도로 증가한다.

순차 탐색 알고리즘이 O(n)의 시간복잡도를 가진다.

O(n log n)

선형 로그 시간복잡도라고도 한다. 로그 시간으로 실행되는 알고리즘 O(log n)을 n번 반복하는 형태를 말하며, O(n log n)으로 표기한다.

보통 데이터 세트를 작은 부분으로 나누고, 이들을 독립적으로 처리하는 형태를 취한다.

병합정렬, 퀵정렬과 같은 효율적인 정렬알고리즘이 선형 로그 시간복잡도를 따른다

O(n^2)

최악의 경우 입력값 n에 대해 제곱으로 수행 시간이 늘어난다. for문이 두 번 충첩되면 이러한 성능이 나온다.

버블정렬, 삽입정렬 등이 O(n^2)의 시간복잡도를 가진다

O(2^n)

최악의 경우 입력값 n에 대해 최대 2의 n제곱만큼 수행 시간이 증가한다.

---

(24262)알고리즘 수업 - 알고리즘의 수행 시간 1

문제에서 주어진 것

MenOfPassion 알고리즘

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

문제에서 구하고자 하는 것

1. 코드 수행 횟수
2. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수 ⇒ 시간복잡도

풀이

입력의 크기 n이 주어질 때, 입력 값에 대해 n / 2 연산을 수행하고, A 배열의 i 번째 값을 return 하므로,

어떠한 n이 주어져도 수행 횟수는 1번이고, 수행횟수를 다항식으로 나타내도 1이므로 최고차항의 차수는 0이다.

---

(24263)알고리즘 수업 - 알고리즘의 수행 시간 2

문제에서 주어진 알고리즘

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

문제에서 구하고자 하는 것

1. 코드 수행 횟수
2. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수 ⇒ 시간복잡도

풀이

주어진 알고리즘은 입력의 크기 n이 주어질 때, for 문을 n번 반복한다. 따라서 연산 횟수는 n번이고, 수행 횟수를 다항식으로 나타내면 n이므로 최고차항의 차수는 1이다.

---

(24264)알고리즘 수업 - 알고리즘의 수행 시간 3

문제에서 주어진 알고리즘

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

문제에서 구하고자 하는 것

1. 코드 수행 횟수
2. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수 ⇒ 시간복잡도

풀이

주어진 알고리즘은 입력의 크기 n이 주어질 때, n번 반복하는 for문이 두번 중첩되어 실행된다. 따라서 시간복잡도는 O(n^2) 이며, 수행횟수는 n^2 번이 되고, 최고차항의 차수는 2가 된다.

---

(24265) 알고리즘 수업 - 알고리즘의 수행 시간 4

문제에서 주어진 알고리즘

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

문제에서 구하고자 하는 것

1. 코드 수행 횟수
2. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수 ⇒ 시간복잡도

풀이

주어진 알고리즘은 1부터 n-1 까지 n-1회 반복하는 for문 안에 다시 i+1부터 n까지 n-i회 반복하면서 A[i] * A[j]의 합을 구하여 출력하는 코드이다.

i = 1 인 경우, j는 2부터 n까지 총 n-1 회

i = 2 인 경우, j는 3부터 n까지 총 n-2회

…

i = n-2 인 경우, j는 n-1부터 n까지 총 2회,

i = n-1 인 경우, j는 n부터 n까지 총 1회

따라서 수행 횟수는 n을 n-1번 더한 수에서 첫째항이 1 ~ 마지막 항이 n-1 인 등차 수열의 합을 빼면 된다.

n(n-1)-(n-1)*n/2 가 된다.

또한 시간 복잡도는 O(n^2)가 되므로 최고차항의 차수는 2이다.

---

(24266)알고리즘 수업 - 알고리즘의 수행 시간 5

문제에서 주어진 알고리즘

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

문제에서 구하고자 하는 것

1. 코드 수행 횟수
2. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수 ⇒ 시간복잡도

풀이

주어진 알고리즘은 입력의 크기 n이 주어질 때, n번 반복하는 for문이 세 번 중첩되어 실행된다. 따라서 시간복잡도는 O(n^3) 이고, 코드 수행 횟수는 n^3번, 최고차항의 차수는 3이다.

---

(24267)알고리즘 수업 - 알고리즘의 수행 시간 6

문제에서 주어진 알고리즘

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

문제에서 구하고자 하는 것

1. 코드 수행 횟수
2. 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수 ⇒ 시간복잡도

풀이

for 문이 세 번 중첩되므로 시간복잡도는 O(n^3) 이 된다. 또한 코드의 실행 횟수는

i = 1, j = 3, k = 4 ~ 7

i = 1, j = 4, k = 5 ~ 7

i = 1, j = 5, k = 6 ~ 7

i = 1, j = 6, k = 7

이 되므로

nC3의 횟수를 가지게 된다. 따라서 수행 횟수를 식으로 나타내보면 n(n-1)(n-2)/6 이 된다.

---

(24313) 알고리즘 수업 - 점근적 표기 1

알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.

함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.

풀이

a_1, a_0 = tuple(map(int,input().split()))
c = int(input())
n_0 = int(input())

def F1(n):
    return a_1*n + a_0

def G1(n):
    return n

result = 0

if F1(i) <= c*G1(i) and a_1 <= c:
    return 1
else :
    return 0