들어가기 전에
많은 양의 데이터를 효율적으로 관리하기 위해 다양한 자료구조 및 알고리즘이 개발되어 왔습니다. 하지만 이 효율적이라는 것의 기준은 무엇일까요? 프로그램의 복잡도를 계산하여 이러한 알고리즘을 비교하는 방법에 대해 살펴보도록 하겠습니다.
학습 목표
작성한 프로그램의 시간 복잡도를 계산하여 알고리즘의 효율성을 비교할 수 있습니다.
핵심 단어
- 시간 복잡도
- 알고리즘 비교
강의 듣기
1-2. 복잡성 소개
시간 복잡도
시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다. 시간 복잡도에는 몇 가지 규칙이 있습니다.
- input \geq≥ 0
- functions do more work
for more input
- drop all constants
- ignore lower order terms
- ignore the base of logs
- 2n = O(n)2n=O(n) => 2n \in O(n)2n∈O(n)
규칙 1. 입력값(n)은 항상 0보다 크다.
입력값이 음수일 수는 없습니다. 그래서 복잡도는 항상 0보다 크다고 가정하고 계산을 해야합니다.
규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 됩니다.
더 많은 입력값이 주어지면 어떤 작업을 하는 데 필요한 계산이나 처리 시간이 길어집니다.
규칙 3. 시간 복잡도에서는 모든 상수를 삭제합니다.
만약 어떤 알고리즘의 복잡도가 3n3n 이라면 3은 고려하지 않고 복잡도는 nn이 됩니다. 2n2n, 3n3n, 10n10n 모두 복잡도가 nn 인 알고리즘입니다.
규칙 4. 낮은 차수의 항들은 무시합니다.
시간 복잡도에서는 nn 과 n^2n2를 비교할 때에는 항상 n^2n2이 더 오래 걸리는 알고리즘이라고 판단합니다. 여기서 의문이 들 수 있는 점은 그래프에서 (1,1)인 지점 전까지는 nn 이 더 오래 걸릴 수 있다는 것입니다. 하지만 알고리즘에서는 입력값( nn )이 1보다 작은 값은 고려하지 않고 큰 값에 대해서만 생각을 하므로 nn 이 무한으로 커진 경우를 가정하고 비교해야 합니다.
이런 이유로 시간 복잡도에서는 낮은 차수의 항들은 무시합니다. n^3 + n^2 + nn3+n2+n 이라는 함수가 있을 때, nn 과 n^2n2은 알고리즘의 시간 복잡도에 영향을 미치지 않고, 입력값이 무한이 될 때 고려해야 할 부분은 n^3n3 입니다. 다음 강의에서 이런 내용을 어떤 형식으로 표현해야 할지 배울 것입니다.
규칙 5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시합니다.
모든 로그는 서로 배수 관계입니다. 그래서 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 됩니다. 로그의 밑은 무시하고 로그 ( lognlogn ) 알고리즘이라고만 말하면 됩니다.
복잡도가 loglog 인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용됩니다. 그래서 만약 for 반복문을 사용해서 무언가를 탐색하면서 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 됩니다. 10으로 나누거나 10을 곱하게 되면 밑이 10인 로그가 됩니다. 하지만 시간 복잡도를 표시할 때에는 로그의 밑은 무시하고 그냥 log n 복잡도를 가진다고 표현합니다.
규칙 6. 등호를 사용하여 표현합니다.
다음 강의에서 더 자세히 다루겠지만 2n2n 은 O(n)O(n) 과 같습니다. 여기서 O(n)O(n) 은 2n2n 이 어떤 함수의 집합에 속한다는 의미를 가집니다. 그렇기 때문에 아래와 같은 등호를 활용하여 이 관계를 수학적으로 쓸 수 있습니다.
2n = O(n), 2n ∈ O(n)
이번 자료 구조 수업을 통해서 여러 종류의 알고리즘을 배우게 될 겁니다. 예를 들어, 상수 시간에 작동하는 알고리즘을 하나 생각해봅시다. 이 알고리즘의 시간 복잡도는 1 또는 문자 C를 사용하여 나타냅니다. 한 번의 계산만 하면 되는 경우로 nn 과는 독립적인 관계를 가집니다. 또, 정렬이나 트리에서는 lognlogn 또는 n^2n2 복잡도인 알고리즘들을 많이 보게 될 것입니다.
생각해보기
1) 시간 복잡도가 1이거나 n인 것은 각각 무엇을 의미할까요?
comment
O(1) -> 입력값 n과 관계 없이 상수 시간의 연산을 보임.
O(n) -> 입력값 n만큼 비례하여 늘어나는 시간의 연산을 보임.
시간복잡도 1 -> 한번의 계산, 상수는 무시한다.
시간복잡도 n -> 예를 들어 연결리스트에서 각 한번씩 모두 순회할 때
시간복잡도 1-> 한번의 계산, 상수는 무시한다.
시간복잡도 n-> 예를 들어 연결리스트에서 각 한번씩 모두 순회할 때
시간 복잡도 1: 입력값과 무관하게 일정한 시간 동작
시간 복잡도 n: 입력값에 비례하여 동작
1. 시간복잡도 1 : 한 번의 계산(n과는 독립적인 관계)으로, 입력값과 상관 없음
2. 시간복잡도 n : 각각의 요소마다 한 번씩 작업 (입력값이 n 이면 n만큼의 시간이 늘어남) n과 비례함 ex) 리스트, 연결리스트
1번 계산
n번 계산
시간복잡도 1-> 같은 복잡도. 계속 시간 1만큼 걸림. input이 뭐든간에
시간복잡도 n -> 시간이 n만큼 걸림. input에 비례해서 늘어남.
시간복잡도 1 : 항상 같은 처리시간
시간복잡도 n : 요소의 개수만큼 긴 처리시간
시간복잡도 n^2 : 모든 요소를 서로 비교할 때 (거품 정렬 알고리즘)
시간복잡도가 1인경우는 입력값과 상관없이 같은 시간이 걸리는것입니다. 입력값이 10이든 100이든 결과값을 반환하는 시간은 같습니다. 시간복잡도가 n인 경우는 입력값에 비례하여 시간이 증가합니다.
입력값의 크기와 상관없이 일정한 시간이 걸리는 경우를 시간복잡도가 1이라고 한다.
입력값의 크기에 비례하여 시간이 늘어나는 경우를 시간복잡도가 n 이라고 한다.
시간복잡도 1 : **입력값** 과 상관없이 일정하게 **시간** 이 걸림
입력값 : 1_000_000_000L
시간복잡도 : 1
시간복잡도 n : **입력값** 에 따라 **시간**이 비례하여 증가
입력값 : 1_000_000_000L
시간복잡도 : 1_000_000_000
시간 복잡도 1 : 입력 값(n)에 상관없이 문제를 해결하기 위한 단계의 수가 일정하다.
시간 복잡도 n : 입력 값(n)이 늘어나는 것에 비례해 문제를 해결하기 위한 단계의 수가 증가한다.
시간 복잡도 1: 입력 값(n)의 크기와 관계없이 일정한 수의 단계만 수행 (일정한 시간이 걸림)
시간 복잡도 n: 입력 값(n)에 따라 시간이 같은 비율로 증가 - 선형 복잡도
시간복잡도 1 : 입력 값( n ) 과 상관없이 일정한 시간이 걸림
시간복잡도 n: 입력 값 ( n ) 에 따라 시간도 ( n ) 만큼 비례하여 증가
1: 입력값과는 상관없이 상수 시간이 걸리는 경우,
n: 입력값에 따라 한번씩 작업한다.
1. 입력값의 크기에 관계없이 반환에 걸린 시간이 일정할 경우
n. 입력값을 처리하기 위해 필요한 최소 반응값
1은 입력에 상관없이 항상 한 번만 하는 것
n 은 입력 데이터가 늘어날 수록 n 만큼 시간이 늘어나는 것
시간복잡도가 1인것은 데이터와 상관없이 항상같은 데이터로 작동하는 로직일 확률이 많을 것 같습니다.
시간복잡도가 n인경우는 입력값이 많으면 많을수록 그에 비례해서 n만큼 시간이 더걸린다는 뜻인것 같습니다.
1) 시간 복잡도가 1이거나 n인 것은 각각 무엇을 의미할까요?
시간 복잡도가 1인 것은 입력 받은 데이터의 양에 상관 없이 항상 일정한 시간이 소요되는 복잡도이다.
데이터가 100개가 들어오던, 100만개가 들어오던 항상 일정.
시간 복잡도가 n인 것은 입력 되는 데이터의 양에 비례하여 시간이 증가하는 복잡도이다.
데이터가 100개 들어오면 100에 비례하는 시간, 100만개가 들어오면 100만에 비례하는 시간이 소요된다.
1) 시간 복잡도가 1이거나 n인 것은 각각 무엇을 의미할까요?
1은 상수 시간에 작동하는 알고리즘의 복잡도. 한 번의 계산만 하면 되는 경우임. n과는 독립적인 관계를 가짐
n은 각각의 요소마다 한 번씩 작업을 하는 경우의 복잡도