Nagie's DevStory

팩토리얼은 양의 정수 n에 대해 n!로 표시되며, 1부터 n까지의 모든 양의 정수를 곱한 값을 나타낸다. 재귀함수와 반복문을 사용해 각각 구현했다. 재귀함수 unsigned long long factorial(int n) { return (n == 0) ? 1 : n * factorial(n - 1); } 반복문 unsigned long long factorial(int n) { unsigned long long sum = 1; for (int i = 1; i

O(n!)은 팩토리얼(Factorial) 시간 복잡도를 나타낸다. 이는 입력 크기 n에 대해 n의 팩토리얼에 비례하는 실행 시간을 가지는 알고리즘을 의미하며, 팩토리얼 시간 복잡도는 굉장히 높은 성능 비용을 가지기 때문에, 큰 입력에 대해서는 사용이 거의 불가능에 가깝다. O(n!)의 알고리즘은 일반적으로 재귀적인 방법을 사용하여 문제를 작은 부분으로 나누고, 모든 가능성을 따져야 하는 경우에 나타나며 대표적인 예시로는 외판원 문제(Travelling Salesman Problem)가 있다. 아래는 재귀함수를 사용해 팩토리얼을 계산하는 코드이며, O(n!) 시간 복잡도를 가진다. int factorial(int n) { if (n == 0 || n == 1) { return 1; } else { retu..

O(n log n)은 로그 선형(Log-Linear) 시간 복잡도를 가지는 알고리즘을 나타낸다. 이는 입력 크기 n에 대해 n과 log n의 곱에 비례하는 실행 시간을 갖는 알고리즘을 의미하며, 주로 효율적인 정렬 알고리즘에서 나타난다. 아래는 가장 널리 사용되는 O(n log n) 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이다. // 두 변수의 값을 교환하는 함수 void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // 배열을 특정한 피벗을 기준으로 두 부분으로 나누고, 피벗의 정확한 위치를 반환 int partition(int arr[], int low, int high) { int pivot = arr[..

O(log n)은 이진 로그(logarithmic) 시간 복잡도를 가지는 알고리즘을 나타낸다. 이는 입력 크기 n에 대해 로그의 형태로 실행 시간이 증가하는 알고리즘을 의미한다. 주로 이진 탐색과 같은 분할 정복 알고리즘에서 발생하며, 큰 데이터셋에서 효과적으로 동작하는 특성 덕에 탐색이나 정렬과 같은 문제에서 자주 사용된다. int binarySearch(int arr[], int left, int right, int target) { while (left

O(2ⁿ)은 입력 크기 n에 대해 2의 n 제곱에 비례하는 지수 시간 복잡도를 갖는 알고리즘을 나타낸다. 이는 입력 크기가 증가함에 따라 실행 시간이 기하급수적으로 증가하는 경우이며, 주로 재귀 알고리즘에서 이러한 시간 복잡도가 발생한다. 아래는 O(2ⁿ)의 시간 복잡도를 가지는 피보나치수열을 구하는 코드이다. int fibonacci(int n) { if (n