Recursion, Sorting, Time Complexity (6/19)
1 Introduction
Энэ хичээлээр бид дараах сэдвүүдийг гүнзгий судална:
- Recursion (Өөрийгөө дууддаг функц)
- Sorting (Өгөгдлийг эрэмбэлэх олон аргачлал)
- Time Complexity (Алгоритмын гүйцэтгэлийн шинжилгээ)
Эдгээр ойлголт нь C++ хэл дээр алгоритм бичихэд чухал ач холбогдолтой бөгөөд олимпиад, competitive programming-д шууд хамаатай.
2 Recursion
2.1 Recursion гэж юу вэ?
Recursion гэдэг нь функц өөрийгөө дуудаж асуудлыг багасгаж шийдэх аргыг хэлнэ. Жишээлбэл, \(n! = n \times (n-1)!\) гэж бичигддэг тул энэ нь recursion ашиглах боломжийг харуулж байна.
2.1.1 Суурь нөхцөл (Base case)
Бүх recursion функц зогсоох нөхцөлтэй байх ёстой. Үгүй бол function stack дуусаж, “stack overflow” алдаа өгнө.
2.1.2 Recursive case
Функц өөрийгөө дуудаж, асуудлыг бага болгож шийддэг хэсэг.
2.2 Example 1: Factorial
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}Жишээ: factorial(5) → 5 * 4 * 3 * 2 * 1 = 120
2.3 Example 2: Fibonacci Number
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}⚠️Анхааруулга: Энэ функц дахин дахин ижил тооцооллоо хийдэг тул удаан ажилладаг. Илүү хурдан аргыг дараа судална.
2.4 Example 3: Reverse a string using recursion
void reverseString(string& s, int i) {
if (i >= s.size() / 2) return;
swap(s[i], s[s.size() - 1 - i]);
reverseString(s, i + 1);
}3 Sorting
Өгөгдлийг тодорхой дарааллаар эрэмбэлэх үйлдлийг sorting гэнэ. Өсөх (ascending) буюу буурах (descending) дараалал байж болно.
3.1 Hand-coded Sorting Algorithms
3.1.1 Bubble Sort
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
}Bubble Sort нь хөрш элементүүдийг харьцуулж, том утгыг “хөөж” ард нь тавьдаг.
3.1.2 Selection Sort
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx])
minIdx = j;
}
swap(arr[i], arr[minIdx]);
}
}3.2 STL ашиглан эрэмбэлэх
3.2.1 Array sort (C-style массив)
#include <algorithm>
sort(arr, arr + n); // ascending sort
sort(arr, arr + n, greater<int>()); // descending3.2.2 Vector sort
vector<int> v = {5, 2, 9, 1};
sort(v.begin(), v.end()); // ascending
sort(v.rbegin(), v.rend()); // descending3.2.3 Custom sort with comparator
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
sort(v.begin(), v.end(), cmp);3.3 Харьцуулалт
| Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) |
| Selection Sort | O(n²) | O(n²) | O(n²) |
STL sort() |
O(n log n) | O(n log n) | O(n log n) |
4 Time Complexity
Алгоритмын ажиллах хугацааг Time Complexity буюу Big-O Notation-оор хэмжинэ.
4.1 Үндсэн Big-O төрлүүд:
- O(1) – Constant Time: үргэлж ижил хугацаа
- O(log n) – Logarithmic: binary search
- O(n) – Linear: нэг удаа давтдаг
- O(n log n) – Efficient sort algorithms
- O(n²) – Давхар давталт
- O(2^n) – Exponential: recursion with branching
4.2 Жишээ 1: O(1)
int getFirst(int arr[]) {
return arr[0];
}4.3 Жишээ 2: O(n)
int linearSum(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}4.4 Жишээ 3: O(n²)
void printPairs(int arr[], int n) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cout << arr[i] << ", " << arr[j] << endl;
}4.5 Жишээ 4: Binary Search – O(log n)
int binarySearch(int arr[], int n, int target) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}4.6 Зөвлөгөө
- Давхар давталт ашиглах хэрэгтэй эсэхийг бодолц.
- STL
sort()ашигласнаар O(n log n) runtime-тэй болно. - Recursion ашиглах үед stack overflow-оос сэргийлж base case заавал бич.
5 Example Programs
5.1 Recursively find the maximum element in array
int findMax(int arr[], int n) {
if (n == 1) return arr[0];
return max(arr[n - 1], findMax(arr, n - 1));
}5.2 Sort names alphabetically
vector<string> names = {"Bold", "Amar", "Tuvshin"};
sort(names.begin(), names.end());5.3 Count how many pairs (i, j) such that i < j and a[i] + a[j] == k
int countPairs(vector<int>& a, int k) {
int count = 0;
int n = a.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] + a[j] == k) count++;
return count;
}5.4 Identify time complexity of code samples
// O(n log n)
sort(arr, arr + n);
// O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
sum += i * j;
// O(log n)
while (n > 1) {
n /= 2;
}5.5 Reverse digits using recursion
void reverseDigits(int n) {
if (n == 0) return;
cout << n % 10;
reverseDigits(n / 10);
}