Asymptotic notation in Computer Algorithms
점근적 표기법
Contents
1️⃣ 알고리즘의 수행시간 (Execution time of an algorithm)
2️⃣ 점근적 분석의 개념 (Concept of asymptotic analysis)
3️⃣ 점근적 표기법 (Asymptotic notation)
4️⃣ 점근적 표기법의 예시 (Examples of asymptotic notation)
1️⃣ 알고리즘의 수행시간
(Execution time of an algorithm)
위의 이미지에서 보여주는 알고리즘은 같은 값을 출력하지만, 접근 방식이 다르다.
설명:
알고리즘 1-1:
직관적으로 구현된 알고리즘이다.
for루프를 통해 1부터n^2까지의 숫자의 합을 직접 구하는 방식이다.시간 복잡도는 루프를 통해 연산을 수행하므로 O(n)이다.
알고리즘 1-2:
공식을 활용한 알고리즘이다. 고등학교 수학에서 배운 공식을 사용하여 1부터
n^2까지의 합을 계산한다.시간 복잡도는 공식 하나로 해결되기 때문에 O(1)로 매우 빠르다.
결론: 알고리즘 1-1은 직관적으로 이해하기 쉬운 반면, 알고리즘 1-2는 공식에 대한 지식이 필요하다. 하지만 효율성 측면에서는 공식(알고리즘 1-2)을 사용하는 것이 훨씬 더 빠르고 효율적이다.
n이 작을 때는 두 알고리즘 간의 성능 차이가 크지 않지만, n이 커질수록 알고리즘 1-2가 훨씬 더 빠르게 처리되는 것을 확인할 수 있다.
이를 통해 알고리즘의 효율성이 중요하다는 것을 알 수 있다. 큰 데이터를 처리할 때는 효율적인 알고리즘이 성능에 큰 차이를 만들 수 있다.
점근적 분석에서는 n의 크기가 커질수록
상수적인 차이(constant difference)는 중요하지 않기 때문에, 각각의 연산 수가 다소 다르더라도, n이 커지면 이러한 상수 차이는 무시된다.O(1)과 같은 상수 시간 알고리즘은 n의 크기와 상관없이 매우 효율적이기 때문에 알고리즘의 성능 비교에서 중요한 요소는 연산 수가 아닌, n에 따른 시간 복잡도이다.
결론적으로, 큰 데이터셋을 다룰 때는 상수배의 연산 차이가 아니라, 시간 복잡도가 더 중요하게 고려된다.
💡상수적인 차이(constant difference): 상수적인 차이란, 입력 크기(n)의 변화와 상관없이 일정한 차이를 의미합니다.
예를 들어, 어떤 알고리즘이 3번의 연산을 하고, 다른 알고리즘이 7번의 연산을 한다면, 그 차이는 항상 4번의 연산. 이 4번의 연산 차이는 입력 크기(n)가 작든 크든 항상 일정하기 때문에 이를 상수적인 차이라고 부른다.
하지만, 알고리즘의 성능을 분석할 때는 입력 크기(n)가 커질수록 중요한 것은 상수적인 차이가 아니라 시간 복잡도이다. n이 커질 때, 3번과 7번의 연산 차이는 전체 성능에 큰 영향을 미치지 않기 때문에, 상수적인 차이는 무시된다.
예시: 알고리즘 A가 5n의 연산을 하고, 알고리즘 B가 10n의 연산을 한다면, 두 알고리즘의 차이는 상수적인 차이인 5n이이다. 하지만 알고리즘 A가 O(n²)의 복잡도를 가지고, 알고리즘 B가 O(n)의 복잡도를 가진다면, n이 매우 커질 때는 복잡도의 차이가 성능에 큰 영향을 미친다. 이때는 상수 차이가 의미가 없어지게 된다. 즉, 상수적인 차이는 n의 크기에 상관없이 고정된 차이를 의미하며, 큰 데이터셋에서 성능을 분석할 때는 중요한 요소가 아니다.
이 이미지는 여러 함수의 증가율을 비교한 그래프이다. 각 함수의 증가율이 어떻게 다른지를 보여주며, 특히 n이 커질수록 어떤 함수들이 더 빠르게 증가하는지를 설명하고 있다. 간단히 설명하면
- 2^n은 매우 빠르게 증가하는 함수로, 비효율적인 알고리즘에서 나타난다.
n^3과 n^2도 n이 커질수록 빠르게 증가하는 편이다.
nlogn과 n은 상대적으로 천천히 증가하며, 효율적인 알고리즘에서 자주 등장하는 복잡도이다.
logn은 n이 커져도 거의 증가하지 않아, 가장 효율적인 함수 중 하나이다.
주요 함수들의 증가율 자세히 설명:
2^n: 기하급수적으로 증가하는 함수로, n이 커질수록 매우 빠르게 증가한다. n이 조금만 커져도 값이 급격히 커지는 특징을 가진다. 알고리즘에서 이런 복잡도는 매우 비효율적이다.
n^3과 n^2:
- 다항식 함수(polynomial function)로, n이 커질수록 빠르게 증가하지만 2^n보다는 덜 급격하게 증가한다. 그래도 n^3은 n^2보다 훨씬 더 빨리 증가한다. n^3은 알고리즘에서 고차 복잡도(High complexity)로 간주되며, 성능에 영향을 많이 미친다.
nlogn:
- nlogn은 n과 로그 함수의 조합으로, n^2보다는 천천히 증가하지만, 선형 함수(n), Linear function 보다는 빠르게 증가한다. 알고리즘에서 자주 등장하는 복잡도로, 퀵소트(Quicksort)와 같은 효율적인 알고리즘의 시간 복잡도를 나타낸다.
n:
- 선형 함수(Linear function)로, n에 비례하여 일정하게 증가한다. 알고리즘에서 효율적인 복잡도로 간주되며, n이 커져도 상대적으로 느리게 증가 한다.
logn:
- 로그 함수로, n이 커질수록 매우 천천히 증가한다. 이는 알고리즘에서 가장 효율적인 시간 복잡도 중 하나로, 이진 탐색(Binary search)과 같은 알고리즘에서 자주 등장한다.
10n: 선형 함수로, n이 증가함에 따라 비교적 일정하게 값이 증가한다. 따라서 큰 n 값에서도 효율적인 성능을 유지할 수 있다.
2n²: 이차 함수(quadratic function)로, n이 증가할수록 값이 기하급수적으로(exponentially) 커진다. 초기에는 10n과 큰 차이가 없지만, n이 커질수록 2n²의 성능이 급격히 떨어진다.
반복문과 함수 호출이 알고리즘의 성능을 결정하는 핵심 요소라고 할 수있다. 이중 반복문(Nested loop) 1-3은 n²에 비례하는 시간이 걸리며, 재귀 호출(Recursive call) 1-4는 n에 비례하는 시간이 소요되는데 이를 통해 알고리즘의 효율성을 판단할 수 있다. 알고리즘의 수행시간을 좌우하는 기준을 자세히 살펴보자
1. For 루프의 반복 횟수: 루프가 몇 번 반복되느냐가 알고리즘의 수행 시간에 큰 영향을 준다. 반복이 많을수록 수행 시간이 길어진다.
2. 특정 행이 수행되는 횟수: 특정 코드가 얼마나 자주 실행되는지도 중요다. 자주 실행되는 코드일수록 전체 성능에 영향을 미치기 때문이다.
3. 함수의 호출 횟수: 함수가 얼마나 자주 호출되는지가 알고리즘 성능에 영향을 미친다. 재귀 호출(Recursive call)이 많은 경우, 호출 횟수가 곧 성능에 영향을 준다.
알고리즘 1-3 (배열의 각 쌍의 곱의 합 계산): 시간 복잡도면에서 이 알고리즘은 중첩된 for 루프가 있으므로, n²에 비례하는 시간이 소요된다. 즉, 이중 루프(nested loop)가 존재해 전체 연산량이 n²에 비례하는 성능을 갖게된다.
알고리즘 1-4 (팩토리얼 함수): 시간 복잡도면에서 이 함수는 자기 자신을 호출하는 재귀 함수로, 입력 값 n에 비례한 횟수만큼 호출된다. 따라서, 이 알고리즘은 n에 비례하는 시간이 소요되게 된다.
2️⃣ 점근적 분석의 개념
(Concept of asymptotic analysis)
💡요약: 점근적 분석(Asymptotic Analysis)은 입력 크기(n)가 매우 클 때 알고리즘의 성능이 어떻게 변화하는지를 분석하는 방법이다. 점근적 분석은 알고리즘의 성능을 예측하고, 입력 크기(n)가 커질 때 어떻게 동작하는지를 분석하는 중요한 도구이다. 특히, Worst case 분석이 가장 널리 사용되고 있다.
1. 점근적 분석의 개념:
- 점근적 분석은 입력 크기가 충분히 클 때 함수가 어떻게 동작하는지를 분석하는 방식이다. 이를 통해 알고리즘의 성능을 예측할 수 있게 된다. 예를 들어,
lim f(n)에서n → ∞는 n이 무한대로 커질 때 함수 f(n)의 값이 어떻게 변화하는지를 나타내고 있다.
2. 점근적 분석의 유형:
Worst case (최악의 경우):
- 알고리즘이 가장 비효율적으로 작동하는 상황을 분석하는 방법이다. 가장 많이 사용되는 분석 방법으로, 성능이 최악의 상황에서 어떻게 변하는지 보여준다.
Average case (평균적인 경우):
- 평균적인 입력에서 알고리즘이 어떻게 작동하는지를 분석한다. 실제 사용 환경에서의 성능을 예측하는 데 도움이 된다.
Best case (최선의 경우):
- 알고리즘이 가장 효율적으로 작동하는 상황을 분석한다. 그러나 컴퓨터 공학에서는 크게 중요하지 않으며, 대부분 Worst case 분석이 더 많이 사용된다.
💡요약: 점근적 표기법 중 가장 널리 사용되는 빅-오(Big-O) 함수에 대한 설명을 살펴본다. 빅-오 표기법은 최악의 경우에 알고리즘이 얼마나 빠르게 증가하는지를 나타내며, 알고리즘의 성능 분석에 필수적인 도구이다.
1. 빅-오 함수 O(g(n)):
정의: 빅-오 함수는 최악의 경우에 함수 g(n)의 비율로 증가하는 함수다.
예시:
O(n): 선형적인 증가(Linear growth)
O(n log n): 로그 선형적인 증가(Log-Linear growth)
O(n²): 이차 함수의 증가(Quadratic growth)
O(2ⁿ): 기하급수적인 증가(Exponential growth)
빅-오 표기법은 이러한 함수들이 알고리즘의 시간 복잡도를 어떻게 표현하는지를 나타낸다.
2. 수학적 정의(Mathematical definition)
f(n) = O(g(n))은 함수 f(n)이 g(n)보다 더 빠르게 증가하지 않음을 의미한다.
정의에 따르면, f(n)은 상수 c와 임계점 n₀를 기준으로 n이 커질수록 g(n)보다 크지 않게 증가해야 한다.
3. 직관적 의미(Intuitive meaning)
- f(n) = O(g(n))은 f(n)이 g(n)보다 더 빠르게 증가하지 않음을 뜻합니다. 즉, 최악의 경우에도 g(n)의 비율로만 증가한다는 것을 의미한다.
빅-오(Big-O) 함수에 대한 설명을 예제와 함께 살펴보자. 알고리즘의 시간 복잡도를 가능한 한 정확하고 tight하게 표현하는 것이 중요하다. 이를 통해 알고리즘 성능을 정확하게 평가하고, 성능 향상을 위한 적절한 개선이 가능해진다.
주요 내용: 빅-오 함수의 예시 (상수는 모두 무시되고 함수에만 집중해서 살펴보자)
O(n²): 3n2+2n3n² + 2n3n2+2n, 7n2−100n7n² - 100n7n2−100n와 같은 함수는 O(n²)로 표현됩니다.
O(nlogn): nlogn+5n, nlogn+logn 와 같은 함수는 O(nlogn)로 표현된다.
O(n): 5n+logn, n+1/n 와 같은 함수는 O(n)로 표현된다.
최대한 tight하게 표기:
예를 들어, nlogn+5n은 O(nlogn)으로 표현할 수 있으며, 이를 O(n²)으로 표현할 필요는 없다.
tight하게 표기하지 않으면, 정보의 손실이 발생하여 알고리즘의 실제 성능을 정확히 평가하지 못할 수 있게된다.
💡요약: 빅-오메가(Ω) 표기법은 알고리즘이 최선의 경우에 보여줄 수 있는 성능의 하한선(lower bound)을 나타낸다. 이는 알고리즘의 최악의 성능을 분석하는 빅-오 표기법과 대칭되는 개념이다. 즉, 알고리즘이 최선의 경우에 어느 정도의 시간 복잡도를 갖는지 보여준다.
1. 수학적 정의 (Mathematical definition)
- f(n) = Ω(g(n))의 수학적 정의는 다음과 같다. 상수 c와 n₀가 존재하여, 모든 n이 n₀ 이상일 때, cg(n) ≤ f(n)이 성립해야 한다. 이는 f(n)이 g(n)보다 느리게 증가하지 않음을 의미한다.
2. 직관적 의미 (Intuitive meaning): f(n) = Ω(g(n))은 f(n)이 g(n)보다 느리게 증가하지 않음을 의미한다. 즉, 알고리즘의 최선의 성능이 g(n) 이상의 성능을 보인다는 뜻이다.
💡요약: 빅-세타 표기법은 알고리즘의 시간 복잡도의 정확한 증가율을 나타낸다. 알고리즘이 g(n)과 같은 비율로 증가하는 함수인데 알고리즘의 성능이 최선, 최악 모두에서 g(n)과 동일한 비율로 증가함을 나타낸다.
수학적 정의: 즉, 빅-세타 함수는 빅-오와 빅-오메가가 모두 성립하는 경우이다. 이는 f(n)이 g(n)보다 빠르게도, 느리게도 증가하지 않고 정확히 같은 비율로 증가함을 뜻한다.
직관적 의미: f(n) = Θ(g(n))은 f(n)이 g(n)과 같은 정도로 증가한다는 것을 의미하는데 즉, 최선과 최악의 경우 모두 g(n)의 비율로 알고리즘이 성장하게 된다.
💡요약: 스몰-오 표기법은 알고리즘의 성능이 g(n) 보다 느리게 증가하는 경우를 나타낸다.
알고리즘이 특정 함수보다 성능이 덜 요구되는 상황을 설명할때 사용된다. 점근적으로(asymptotically) g(n)보다 항상 작은 성능을 갖는 함수들을 표현한다.
수학적 정의: n이 무한대로 커질 때 f(n)이 g(n)보다 느리게 증가한다는 것을 의미한다.
직관적 의미: f(n) = o(g(n))은 f(n)이 g(n)보다 느리게 증가한다는 의미이다. 따라서 f(n)의 증가율이 g(n)에 비해 항상 작은 비율로 증가하게 된다.
💡점근적으로(asymptotically) n이 매우 커질 때 어떤 함수나 알고리즘이 어떻게 동작하는지를 표현하는 용어이다. 수학이나 알고리즘 분석에서 주로 사용되는 용어이다.
어떤 함수가 무한히 커질 때, 다른 함수에 가까워지는 방식을 설명할 때 사용된다.
입력 크기(n)가 매우 커질 때, 특정 함수나 알고리즘의 성능이나 행동을 설명하는 데 사용된다.
💡요약: 스몰-오메가 함수 (ω) 표기법은 알고리즘의 성능이 다른 함수보다 더 빠르게 증가할 때 사용된다. 이는 g(n)보다 항상 더 빠르게 증가하는 함수를 나타낸다. 이는 점근적으로 g(n)보다 항상 더 큰 성능을 갖는 함수들을 설명할 때 사용되며, 알고리즘의 성장 속도가 더 빠른 경우를 표현한다.
수학적 정의: n이 무한대로 커질 때 f(n)이 g(n)보다 훨씬 더 빠르게 증가한다는 것을 의미함
직관적 의미: f**(n) = ω(g(n))은 f(n)이 g(n)보다 더 빠르게 증가한다는 의미. 따라서 f(n)의 증가율이 g(n)**보다 훨씬 더 빠르게 커진다.
💡점근적 표기법 요약 💡
각 점근적 표기법의 의미를 간략하게 정리해보자.
점근적 표기법(Asymptotic Notation)은 알고리즘의 성능을 분석할 때 사용하는 방법으로, 각각의 표기법이 성능을 상한선, 하한선, 경계선으로 어떻게 설명하는지 보여준다.
빅-오와 빅-오메가는 각각 상한선과 하한선을 나타내며, 알고리즘 성능의 최악과 최선을 분석할 때 사용된다.
빅-세타는 상한선과 하한선이 정확히 일치하는 경우 사용된다.
스몰-오와 스몰-오메가는 상한선과 하한선이 느슨하게 정의될 때 사용되며, 정확도는 상대적으로 떨어진다.
1. 빅-오 (O(g(n))):
의미: 알고리즘의 성능이 g(n)과 같거나 그보다 느리게 증가할 때, 이를 빅-오로 표기한다.
빠듯하거나 느슨한 상한선을 의미한다. 즉, 최악의 경우 성능을 나타낸다.
2. 빅-오메가 (Ω(g(n))):
- 의미: 알고리즘의 성능이 g(n)과 같거나 그보다 빠르게 증가할 때, 이를 빅-오메가로 표기한다.
- 빠듯하거나 느슨한 하한선을 의미한다. 즉, 최선의 경우 성능을 나타낸다.
3. 빅-세타 (Θ(g(n))):
의미: 알고리즘의 성능이 g(n)과 정확히 같을 때, 이를 빅-세타로 표기한다.
빠듯한 경계선을 의미한다. 즉, 알고리즘의 성능이 상한과 하한에서 모두 g(n)과 같을 때 사용된다.
4. 스몰-오 (o(g(n))):
의미: 알고리즘의 성능이 g(n)보다 느리게 증가할 때 사용한다.
느슨한 상한선으로, 정확한 상한선은 아니지만 g(n)보다는 빠르게 증가하지 않음을 의미한다.
5. 스몰-오메가 (ω(g(n))):
의미: 알고리즘의 성능이 g(n)보다 빠르게 증가할 때 사용한다.
느슨한 하한선으로, 정확한 하한선은 아니지만 g(n)보다 더 느리게 증가하지 않음을 의미한다.
💡 요약: 다양한 정렬 알고리즘(sorting algorithm)에서의 시간 복잡도를 알아보자. 퀵 정렬과 힙 정렬이 상대적으로 효율적이라는 것을 보여주는 그래프이다 . 버블 정렬, 삽입 정렬, 선택 정렬은 입력 크기가 커질수록 성능이 급격히 떨어지므로 큰 데이터에서는 비효율적이다. n log n 복잡도를 갖는 알고리즘이 더 큰 데이터에서 성능이 뛰어난다. 기수 정렬과 계수 정렬은 특정 조건에서 매우 빠른 성능을 보여주며, n log n 복잡도를 가진 알고리즘보다 효율적일 수 있다. 그러나 이 두 정렬 알고리즘은 입력 데이터의 특성에 따라 제한이 있을 수 있다. 즉, 숫자나 정수 범위에 맞는 데이터에서는 효과적이지만, 일반적인 모든 정렬 상황에서 항상 효율적이지는 않다.
주요 내용:
정렬 알고리즘의 시간 복잡도:
버블 정렬, 삽입 정렬, 선택 정렬: 시간 복잡도: O(n²)
- 이 정렬 알고리즘들은 이차 함수처럼 작동하며, n이 커질수록 성능이 급격히 저하된다.
힙 정렬: 시간 복잡도: O(n log n)
- 이 알고리즘은 로그 선형적(log-linear)으로 동작하여, O(n²) 알고리즘보다 훨씬 효율적이다.
퀵 정렬:
최악의 시간 복잡도: O(n²)
평균 시간 복잡도: Θ(n log n)
퀵 정렬은 최악의 경우 O(n²)이지만, 일반적으로 매우 효율적이며 평균적으로 n log n 시간 복잡도를 가진다.
그래프 분석:
그래프에서 각 함수의 증가율을 비교하고 있습니다.
2ⁿ: 기하급수적으로 증가하는 함수.
n³, n²: 다항식 함수(Polynomial Function)로, 입력이 커질수록 성능이 매우 저하됩니다.
n log n: 로그 선형적(Log-linear)인 함수로, 효율적인 알고리즘에서 자주 등장한다.
n: 선형적인 함수로, 가장 이상적인 성능을 나타낸다.
위의 이미지는 저장 및 탐색에서 공간 복잡도의 예시를 보여주고 있다. 여러 자료 구조의 시간 복잡도와 공간 복잡도를 비교하며, 다양한 자료 구조가 데이터 검색이나 저장 작업을 처리하는 데 얼마나 효율적인지 설명하고 있다.
일차원 배열(One-dimensional array)은 선형 탐색이 필요하므로 시간 복잡도가 O(n)으로 비효율적이다.
이진 탐색 트리(Binary search tree)는 평균적으로 log n의 성능을 가지지만, 최악의 경우에는 n까지 떨어질 수 있다.
B-트리는 항상 log n의 성능을 보장하며, 대규모 데이터 탐색에 적합하다.
해시 테이블(Hash table)은 평균적으로 매우 빠르지만, 충돌이 많이 발생하면 성능이 저하될 수 있다.
따라서, 선택할 자료 구조는 데이터의 크기와 탐색 성능 요구사항에 따라 달라진다.
1. 일차원 배열(One-dimensional array) 시간 복잡도: O(n)
- 배열에서 데이터를 탐색하는 경우, n개의 원소를 모두 확인해야 하므로 시간 복잡도가 O(n)이다.
2. 이진 탐색 트리 (Binary Search Tree) 최악의 경우: Θ(n), 평균: Θ(log n)
- 이진 탐색 트리는 정렬된 데이터를 탐색하는 데 매우 효율적이며, 평균적으로 log n 시간에 탐색을 수행할 수 있다. 하지만 트리가 한쪽으로 치우친 경우(편향 트리,skewed tree), 최악의 경우 시간 복잡도는 n이 될 수 있다.
3. B-트리 최악의 경우 Θ(log n)
- B-트리는 대규모 데이터를 처리하기 위한 균형 잡힌 트리이다. 탐색, 삽입, 삭제 등의 작업에서 최악의 경우에도 log n 시간 복잡도를 가진다.
4. 해시 테이블 평균: Θ(n)
- 해시 테이블은 데이터를 상수 시간(O(1))에 검색할 수 있지만, 충돌이 많이 발생하면 성능이 떨어져 n에 비례한 성능 저하가 발생할 수 있다. 그러나 평균적으로는 해시 테이블의 탐색 성능은 매우 우수하다.
이미지는 일차원 배열에서 특정한 원소를 찾는 경우에 대해 설명하고 있으며, 순차 탐색(Linear Search)과 이진 탐색(Binary Search)의 시간 복잡도를 비교하고 있다.
순차 탐색은 배열이 정렬되지 않았을 때 사용할 수 있는 방법이지만, 시간 복잡도가
선형(linear)이기 때문에 큰 배열에서는 비효율적이다.이진 탐색은 배열이 정렬되어 있을 때 사용할 수 있으며, 로그 시간 복잡도를 갖기 때문에 매우 효율적이다. 따라서 큰 데이터셋에서는 이진 탐색이 훨씬 빠르고 효율적인 방법이다.
1. 순차 탐색 (Linear Search):
특징: 배열이 아무렇게나 저장되어 있을 때, 즉 정렬되지 않은 배열에서 특정 원소를 찾기 위해 처음부터 끝까지 하나씩 확인하는 탐색 방법이다.
Worst case (최악의 경우): Θ(n)
- 배열의 마지막 원소를 찾거나, 찾고자 하는 값이 배열에 없을 때, 배열의 모든 원소를 확인해야 하므로 선형 시간이 걸린다.
Average case (평균적인 경우): Θ(n)
- 평균적으로도 배열의 절반 이상을 확인해야 하기 때문에, 평균적으로 n번의 비교가 필요하다.
2. 이진 탐색 (Binary Search):
특징: 배열이 정렬되어 있을 때 사용하는 효율적인 탐색 방법이다. 배열을 절반씩 나누어가며 찾고자 하는 원소가 어느 절반에 속하는지 확인하는 방식이다.
Worst case (최악의 경우): Θ(log n)
- 배열의 크기가 절반씩 줄어들기 때문에 로그 시간 복잡도를 가진다. 즉, 크기가 n인 배열에서 원소를 찾기 위해서는 최대 log n번의 비교가 필요하다.
Average case (평균적인 경우): Θ(log n)
- 평균적으로도 배열을 계속 절반으로 나누기 때문에 평균적으로 log n번의 비교가 필요하다.
💡선형(linear) 직선의 형태를 따르는 또는 직선적인 방식으로 증가하거나 변화하는 것을 의미한다. 수학이나 컴퓨터 과학에서는, 선형적이라는 표현은 입력 크기(n)에 비례하여 시간이 증가하거나 감소하는 것을 나타낸다.
