시간복잡도

hrj2233·2023년 3월 9일
0

data structure

목록 보기
1/1

시간 복잡도

시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다. 시간 복잡도에는 몇 가지 규칙이 있습니다.

  • input ≥ 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)

규칙 1. 입력값(n)은 항상 0보다 크다.

  • 입력값이 음수일 수는 없습니다. 그래서 복잡도는 항상 0보다 크다고 가정하고 계산을 해야합니다.

규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 됩니다.

  • 더 많은 입력값이 주어지면 어떤 작업을 하는 데 필요한 계산이나 처리 시간이 길어집니다.

규칙 3. 시간 복잡도에서는 모든 상수를 삭제합니다.

  • 만약 어떤 알고리즘의 복잡도가 3n3n 이라면 3은 고려하지 않고 복잡도는 nn이 됩니다. 2n2n, 3n3n, 10n10n 모두 복잡도가 nn 인 알고리즘입니다.

규칙 4. 낮은 차수의 항들은 무시합니다.

  • 입력 크기에 비해 작은 항은 무시해도 된다는 것을 의미합니다. 예를 들어, 알고리즘의 시간 복잡도가 100n^3 + 500n^2 + 1000n + 2000이라면, 이를 간단히 O(n^3)으로 나타낼 수 있습니다.

규칙 5. 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시합니다.

  • 모든 로그는 서로 배수 관계입니다. 그래서 복잡도에 관해서 이야기할 때는 로그의 밑에 대해서는 고려하지 않아도 됩니다. 로그의 밑은 무시하고 로그 (logn)알고리즘이라고만 말하면 됩니다.

  • 복잡도가 logn 인 알고리즘은 보통 무언가를 반으로 나누거나 2를 곱한 경우에 자주 사용됩니다. 그래서 만약 for 반복문을 사용해서 무언가를 탐색하면서 반으로 나누거나 2를 곱할 때 복잡도는 밑이 2인 로그가 됩니다. 10으로 나누거나 10을 곱하게 되면 밑이 10인 로그가 됩니다. 하지만 시간 복잡도를 표시할 때에는 로그의 밑은 무시하고 그냥 log n 복잡도를 가진다고 표현합니다.

규칙 6. 등호를 사용하여 표현합니다.

  • 2n이 O(n)에 속한다는 것을 의미합니다. 이는 입력 크기가 커질수록 2n은 n에 비해 무시할 수 있는 정도로 작아지기 때문입니다.

0개의 댓글