복잡성 소개
들어가기 전에
많은 양의 데이터를 효율적으로 관리하기 위해 다양한 자료구조 및 알고리즘이 개발되어 왔습니다. 하지만 이 효율적이라는 것의 기준은 무엇일까요? 프로그램의 복잡도를 계산하여 이러한 알고리즘을 비교하는 방법에 대해 살펴보도록 하겠습니다.
학습 목표
작성한 프로그램의 시간 복잡도를 계산하여 알고리즘의 효율성을 비교할 수 있습니다.
핵심 단어
- 시간 복잡도
- 알고리즘 비교
시간 복잡도
시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다. 시간 복잡도에는 몇 가지 규칙이 있습니다.
- 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인 것은 각각 무엇을 의미할까요?
나의 생각 : 1인 것은 인풋을 추가해도 1번만 사용하는것이고 n은 인풋이 증가하면 시간도 증가한다는 뜻이다.
출처 : https://www.boostcourse.org/cs204/lecture/480344?isDesc=false 네이버커넥트재단