# 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)
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727233769656/59c60e2a-4181-4d9c-8e09-ca6d73f08cac.png align="center")
위의 이미지에서 보여주는 알고리즘은 같은 값을 출력하지만, 접근 방식이 다르다.
**설명:**
1. **알고리즘 1-1**:
* **직관적으로 구현된 알고리즘**이다. `for` 루프를 통해 1부터 `n^2`까지의 숫자의 합을 직접 구하는 방식이다.
* 시간 복잡도는 루프를 통해 연산을 수행하므로 **O(n)**이다.
2. **알고리즘 1-2**:
* **공식을 활용한 알고리즘**이다. 고등학교 수학에서 배운 공식을 사용하여 1부터 `n^2`까지의 합을 계산한다.
* 시간 복잡도는 공식 하나로 해결되기 때문에 **O(1)**로 매우 빠르다.
**결론:** 알고리즘 1-1은 직관적으로 이해하기 쉬운 반면, 알고리즘 1-2는 공식에 대한 지식이 필요하다. 하지만 효율성 측면에서는 공식(알고리즘 1-2)을 사용하는 것이 훨씬 더 빠르고 효율적이다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727233823394/18485708-f48d-4743-84dc-12220ca41223.png align="center")
1. n이 작을 때는 두 알고리즘 간의 성능 차이가 크지 않지만, n이 커질수록 **알고리즘 1-2**가 **훨씬 더 빠르게** 처리되는 것을 확인할 수 있다.
2. 이를 통해 **알고리즘의 효율성**이 중요하다는 것을 알 수 있다. 큰 데이터를 처리할 때는 **효율적인 알고리즘**이 성능에 큰 차이를 만들 수 있다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727234006100/a975a6d8-dfd5-475c-adb5-7d115734d719.png align="center")
* **점근적 분석**에서는 **n의 크기**가 커질수록 `상수적인 차이(constant difference)`는 중요하지 않기 때문에, 각각의 연산 수가 다소 다르더라도, n이 커지면 이러한 상수 차이는 무시된다.
* **O(1)**과 같은 상수 시간 알고리즘은 n의 크기와 상관없이 매우 효율적이기 때문에 **알고리즘의 성능 비교**에서 중요한 요소는 **연산 수가 아닌, n에 따른 시간 복잡도**이다.
결론적으로, **큰 데이터셋**을 다룰 때는 상수배의 연산 차이가 아니라, **시간 복잡도**가 더 중요하게 고려된다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727234691693/a52fa04d-2a1c-49b4-aa19-e139a03568ba.png align="center")
💡`상수적인 차이(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의 크기에 상관없이 **고정된 차이**를 의미하며, 큰 데이터셋에서 성능을 분석할 때는 중요한 요소가 아니다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727234833022/2a748025-4700-48fd-ae0b-e4d65ca8312e.png align="center")
이 이미지는 여러 함수의 **증가율**을 비교한 그래프이다. 각 함수의 증가율이 어떻게 다른지를 보여주며, 특히 **n이 커질수록** 어떤 함수들이 더 빠르게 증가하는지를 설명하고 있다. 간단히 설명하면
* **2^n**은 매우 빠르게 증가하는 함수로, 비효율적인 알고리즘에서 나타난다.
* **n^3**과 **n^2**도 n이 커질수록 빠르게 증가하는 편이다.
* **nlogn**과 **n**은 상대적으로 천천히 증가하며, **효율적인 알고리즘**에서 자주 등장하는 복잡도이다.
* **logn**은 n이 커져도 거의 증가하지 않아, 가장 효율적인 함수 중 하나이다.
**주요 함수들의 증가율 자세히 설명:**
1. **2^n**: **기하급수적으로** 증가하는 함수로, n이 커질수록 매우 빠르게 증가한다. **n이 조금만 커져도 값이 급격히 커지는** 특징을 가진다. 알고리즘에서 이런 복잡도는 매우 비효율적이다.
2. **n^3**과 **n^2**:
* **다항식 함수(polynomial function)**로, n이 커질수록 빠르게 증가하지만 2^n보다는 덜 급격하게 증가한다. 그래도 n^3은 n^2보다 훨씬 더 빨리 증가한다. **n^3**은 알고리즘에서 **고차 복잡도(High complexity)**로 간주되며, 성능에 영향을 많이 미친다.
3. **nlogn**:
* **nlogn**은 n과 로그 함수의 조합으로, **n^2**보다는 천천히 증가하지만, **선형 함수(n), Linear function** 보다는 빠르게 증가한다. 알고리즘에서 자주 등장하는 복잡도로, **퀵소트(Quicksort)**와 같은 효율적인 알고리즘의 시간 복잡도를 나타낸다.
4. **n**:
* **선형 함수(Linear function)**로, n에 비례하여 일정하게 증가한다. 알고리즘에서 **효율적인 복잡도**로 간주되며, n이 커져도 상대적으로 느리게 증가 한다.
5. **logn**:
* **로그 함수**로, n이 커질수록 매우 천천히 증가한다. 이는 알고리즘에서 **가장 효율적인** 시간 복잡도 중 하나로, **이진 탐색(Binary search)**과 같은 알고리즘에서 자주 등장한다.
---
![Uploaded image](https://files.oaiusercontent.com/file-ssKI4bheQ0oUDLuVIcao2pD2?se=2024-09-25T03%3A32%3A02Z&sp=r&sv=2024-08-04&sr=b&rscc=max-age%3D299%2C%20immutable%2C%20private&rscd=attachment%3B%20filename%3Dimage.png&sig=jVIUNm1hc0ul4cksTD10Gxw55ShW%2BN//0GcaVYu38zo%3D align="left")
* **10n**: 선형 함수로, n이 증가함에 따라 비교적 **일정하게** 값이 증가한다. 따라서 큰 n 값에서도 **효율적인 성능**을 유지할 수 있다.
* **2n²**: **이차 함수(quadratic function)**로, n이 증가할수록 값이 **기하급수적으로(exponentially) 커진다**. 초기에는 10n과 큰 차이가 없지만, n이 커질수록 **2n²의 성능이 급격히 떨어진다.**
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727235296126/632f80b2-5515-4d1e-81d2-63d9e1d76e53.png align="center")
**반복문과 함수 호출**이 알고리즘의 성능을 결정하는 핵심 요소라고 할 수있다. **이중 반복문(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)
![Uploaded image](https://files.oaiusercontent.com/file-jkrFwZNnIYPfd5KcOhk8n7x5?se=2024-09-25T03%3A45%3A30Z&sp=r&sv=2024-08-04&sr=b&rscc=max-age%3D299%2C%20immutable%2C%20private&rscd=attachment%3B%20filename%3Dimage.png&sig=yUV%2By%2BXvE4NzoxZTZzTE9YGvApG4XrcD7p3rYfvPSmk%3D align="left")
💡**요약: 점근적 분석(Asymptotic Analysis)**은 **입력 크기(n)가 매우 클 때** 알고리즘의 성능이 어떻게 변화하는지를 분석하는 방법이다. 점근적 분석은 **알고리즘의 성능을 예측**하고, 입력 크기(n)가 커질 때 어떻게 동작하는지를 분석하는 중요한 도구이다. 특히, **Worst case 분석**이 가장 널리 사용되고 있다.
1\. **점근적 분석의 개념**:
* 점근적 분석은 **입력 크기가 충분히 클 때** 함수가 어떻게 동작하는지를 분석하는 방식이다. 이를 통해 알고리즘의 **성능을 예측**할 수 있게 된다. 예를 들어, `lim f(n)`에서 `n → ∞`는 n이 무한대로 커질 때 함수 f(n)의 값이 어떻게 변화하는지를 나타내고 있다.
2\. **점근적 분석의 유형**:
* **Worst case (최악의 경우)**:
* 알고리즘이 가장 비효율적으로 작동하는 상황을 분석하는 방법이다. **가장 많이 사용**되는 분석 방법으로, 성능이 **최악의 상황**에서 어떻게 변하는지 보여준다.
* **Average case (평균적인 경우)**:
* 평균적인 입력에서 알고리즘이 어떻게 작동하는지를 분석한다. 실제 사용 환경에서의 성능을 예측하는 데 도움이 된다.
* **Best case (최선의 경우)**:
* 알고리즘이 가장 효율적으로 작동하는 상황을 분석한다. 그러나 컴퓨터 공학에서는 **크게 중요하지 않으며**, 대부분 Worst case 분석이 더 많이 사용된다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727236272099/5ec287e8-43a0-48a9-a5db-d3a95c024605.png align="center")
💡**요약: 점근적 표기법** 중 가장 널리 사용되는 **빅-오(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)의 비율로만 증가한다는 것을 의미한다.
---
![Uploaded image](https://files.oaiusercontent.com/file-rGQqcOioAeRJAfNpMdaxD5Hu?se=2024-09-25T04%3A04%3A36Z&sp=r&sv=2024-08-04&sr=b&rscc=max-age%3D299%2C%20immutable%2C%20private&rscd=attachment%3B%20filename%3Dimage.png&sig=hmCuOReu9kMkmVYjr8rA/psJnRSuyL9HTAyCLUpCmUY%3D align="left")
**빅-오(Big-O) 함수**에 대한 설명을 예제와 함께 살펴보자. 알고리즘의 **시간 복잡도를 가능한 한 정확하고 tight하게 표현하는 것**이 중요하다. 이를 통해 **알고리즘 성능을 정확하게 평가**하고, 성능 향상을 위한 적절한 개선이 가능해진다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727237057518/64bfc112-4819-4c26-95f6-5eaf702c4bbf.png align="center")
**주요 내용: 빅-오 함수의 예시 (상수는 모두 무시되고 함수에만 집중해서 살펴보자)**
1. * **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)로 표현된다.
2. **최대한 tight하게 표기**:
* 예를 들어, nlogn+5n은 **O(nlogn)**으로 표현할 수 있으며, 이를 **O(n²)**으로 표현할 필요는 없다.
* **tight하게** 표기하지 않으면, **정보의 손실**이 발생하여 알고리즘의 실제 성능을 정확히 평가하지 못할 수 있게된다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727238583206/be88dd29-a198-482a-8d5c-469f9bb3b57f.png align="center")
💡**요약: 빅-오메가(Ω) 표기법**은 알고리즘이 **최선의 경우**에 보여줄 수 있는 성능의 **하한선(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) 이상의 성능**을 보인다는 뜻이다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727238826276/2964e741-a147-4d4b-b270-2aa437319907.png align="center")
💡**요약: ** **빅-세타 표기법**은 알고리즘의 **시간 복잡도의 정확한 증가율**을 나타낸다. 알고리즘이 **g(n)과 같은 비율로 증가하는 함수인데** 알고리즘의 **성능이 최선, 최악 모두**에서 **g(n)**과 동일한 비율로 증가함을 나타낸다.
**수학적 정의**: 즉, **빅-세타 함수**는 **빅-오**와 **빅-오메가**가 모두 성립하는 경우이다. 이는 **f(n)**이 **g(n)**보다 빠르게도, 느리게도 증가하지 않고 **정확히 같은 비율로 증가**함을 뜻한다.
**직관적 의미**: **f(n) = Θ(g(n))**은 **f(n)**이 **g(n)**과 **같은 정도로 증가**한다는 것을 의미하는데 즉, 최선과 최악의 경우 모두 **g(n)**의 비율로 알고리즘이 성장하게 된다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727239525398/07f2da8d-a600-4fc2-bfd3-5d1bee38ade5.png align="center")
💡**요약: 스몰-오 표기법**은 **알고리즘의 성능이 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)가 매우 커질 때**, 특정 함수나 알고리즘의 **성능이나 행동을 설명**하는 데 사용된다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727239844270/2c0067d3-f868-43a7-a3b2-0547344277ee.png align="center")
💡**요약: 스몰-오메가 함수 (ω)** 표기법은 **알고리즘의 성능이 다른 함수보다 더 빠르게 증가**할 때 사용된다. 이는 **g(n)보다 항상 더 빠르게 증가하는 함수**를 나타낸다. 이는 **점근적으로 g(n)보다 항상 더 큰 성능**을 갖는 함수들을 설명할 때 사용되며, **알고리즘의 성장 속도가 더 빠른 경우**를 표현한다.
**수학적 정의**: **n**이 무한대로 커질 때 **f(n)**이 **g(n)**보다 훨씬 더 빠르게 증가한다는 것을 의미함
**직관적 의미**: **f****(n) = ω(g(n))**은 **f(n)**이 **g(n)**보다 **더 빠르게 증가**한다는 의미. 따라서 **f(n)**의 증가율이 **g(n)**보다 훨씬 더 빠르게 커진다.
---
💡**점근적 표기법 요약** 💡
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727240024724/382c93c8-f372-4874-be26-c1408c951cdf.png align="center")
**각 점근적 표기법의 의미**를 간략하게 정리해보자.
**점근적 표기법(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)보다 더 느리게 증가하지 않음을 의미**한다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727240528635/9e746a1f-7810-47b0-9e46-646e3edaf13c.png align="center")
**💡 요약: ** 다양한 정렬 알고리즘(sorting algorithm)에서의 시간 복잡도를 알아보자. **퀵 정렬과 힙 정렬**이 상대적으로 효율적이라는 것을 보여주는 그래프이다 . **버블 정렬, 삽입 정렬, 선택 정렬**은 입력 크기가 커질수록 성능이 급격히 떨어지므로 큰 데이터에서는 비효율적이다. **n log n** 복잡도를 갖는 알고리즘이 더 큰 데이터에서 성능이 뛰어난다. 기수 정렬과 계수 정렬은 **특정 조건에서 매우 빠른** 성능을 보여주며, **n log n** 복잡도를 가진 알고리즘보다 효율적일 수 있다. 그러나 이 두 정렬 알고리즘은 **입력 데이터의 특성에 따라 제한**이 있을 수 있다. 즉, **숫자나 정수 범위에 맞는 데이터**에서는 효과적이지만, 일반적인 모든 정렬 상황에서 항상 효율적이지는 않다.
**주요 내용:**
1. **정렬 알고리즘의 시간 복잡도**:
* **버블 정렬, 삽입 정렬, 선택 정렬: 시간 복잡도**: O(n²)
* 이 정렬 알고리즘들은 **이차 함수**처럼 작동하며, n이 커질수록 성능이 급격히 저하된다.
* **힙 정렬**: **시간 복잡도**: O(n log n)
* 이 알고리즘은 **로그 선형적(log-linear)**으로 동작하여, O(n²) 알고리즘보다 훨씬 효율적이다.
* **퀵 정렬**:
* **최악의 시간 복잡도**: O(n²)
* **평균 시간 복잡도**: Θ(n log n)
* 퀵 정렬은 최악의 경우 O(n²)이지만, 일반적으로 매우 효율적이며 평균적으로 **n log n** 시간 복잡도를 가진다.
2. **그래프 분석**:
* 그래프에서 각 함수의 증가율을 비교하고 있습니다.
* **2ⁿ**: 기하급수적으로 증가하는 함수.
* **n³, n²**: 다항식 함수(Polynomial Function)로, 입력이 커질수록 성능이 매우 저하됩니다.
* **n log n**: 로그 선형적(Log-linear)인 함수로, 효율적인 알고리즘에서 자주 등장한다.
* **n**: 선형적인 함수로, 가장 이상적인 성능을 나타낸다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727242845125/702c88bd-3712-4f5c-99fb-1dac93e32fc5.png align="center")
위의 이미지는 **저장 및 탐색**에서 **공간 복잡도의 예시**를 보여주고 있다. 여러 자료 구조의 **시간 복잡도와 공간 복잡도**를 비교하며, 다양한 자료 구조가 데이터 검색이나 저장 작업을 처리하는 데 얼마나 효율적인지 설명하고 있다.
* **일차원 배열(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**에 비례한 성능 저하가 발생할 수 있다. 그러나 **평균적으로**는 해시 테이블의 탐색 성능은 매우 우수하다.
---
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1727243417107/158aa5e0-5660-4bbd-ac5a-8da1462b4c01.png align="center")
이미지는 **일차원 배열에서 특정한 원소를 찾는 경우**에 대해 설명하고 있으며, **순차 탐색(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)**에 비례하여 시간이 증가하거나 감소하는 것을 나타낸다.
---