Data Structures
A data structure is a way of organizing and storing data in a computer so that it can be accessed and modified efficiently. It defines the relationship between elements within a collection.
Algorithms
An algorithm is a well-defined computational procedure that takes input values and produces output values. Essentially, it's a sequence of steps used to trensform input into desired results.
Algorithm Efficiency
The efficiency of an algorithm refers to how quickly it runs. This is typically measured by timing how long a program takes to execute on a machine. While modern computers have abundant memory, understanding algorithmic efficiency remains crucial for optimizing performance. A well-written program should consider both time and space complexity when evaluating its effectiveness.
Time Complexity
Definition
Time complexity quantifies the amount of time an algorithm takes to run as a function of the input size. Since exact execution times are difficult to determine theoretically, we use asymptotic notation like Big O to describe growth rates rather than precise measurements.
Example Analysis
Consider the following function:
void processArray(int N)
{
int counter = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
++counter;
}
}
for (int k = 0; k < 2 * N; ++k)
{
++counter;
}
int M = 10;
while (M--)
{
++counter;
}
printf("%d\n", counter);
}
The total number of operations follows the pattern F(N) = N² + 2N + 10. Using Big O notation, we simplify this to O(N²), focusing on the dominant term.
Big O Notation Principles
Big O notation expresses how a algorithm's runtime scales with input size:
- O(1): Constant time
- O(log N): Logarithmic time
- O(N): Linear time
- O(N log N): Linearithmic time
- O(N²): Quadratic time
- O(N^k): Polynomial time
- O(2^N): Exponential time
- O(N!): Factorial time
These notations help compare algorithms' performance characteristics without needing specific hardware measurements.
Common Examples
Linear Function
void linearProcess(int N)
{
int counter = 0;
for (int k = 0; k < 2 * N; ++k)
{
++counter;
}
int M = 10;
while (M--)
{
++counter;
}
printf("%d\n", counter);
}
This has a time complexity of O(N).
Multiple Variables
void multiVariableProcess(int N, int M)
{
int counter = 0;
for (int k = 0; k < M; ++k)
{
++counter;
}
for (int k = 0; k < N; ++k)
{
++counter;
}
printf("%d\n", counter);
}
Complexity depends on the relationship between N and M, potentially being O(N), O(M), or O(N + M).
Constant Loop
void constantLoop(int N)
{
int counter = 0;
for (int k = 0; k < 100; ++k)
{
++counter;
}
printf("%d\n", counter);
}
Despite 100 iterations, this remains O(1) because the number of operations is fixed regardless of input size.
Binary Search
int binarySearch(int* array, int length, int target)
{
int start = 0;
int end = length - 1;
while (start <= end)
{
int middle = start + ((end - start) >> 1);
if (array[middle] < target)
start = middle + 1;
else if (array[middle] > target)
end = middle - 1;
else
return middle;
}
return -1;
}
This algorithm achieves O(log N) complexity due to halving the search space at each step.
Recursive Factorial
long long factorial(int N)
{
if (0 == N)
return 1;
return factorial(N - 1) * N;
}
This recursive implementation has O(N) time complexity due to N recursive calls.
Fibonacci Sequence
long long fibonacci(int N)
{
if (N < 3)
return 1;
return fibonacci(N - 1) + fibonacci(N - 2);
}
The naive recursive approach results in exponential time complexity O(2^N) due to repeated calculations.
Space Complexity
Space complexity measures the additional memory required by an algorithm during execution. Unlike time complexity, which focuses on execution duration, space complexity counts the number of variables allocated.
Example Analysis
Bubble Sort
void bubbleSort(int* array, int size)
{
assert(array);
for (size_t end = size; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (array[i - 1] > array[i])
{
swap(&array[i - 1], &array[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
This function uses only a constant amount of extra space, making it O(1) in terms of space complexity.
Fibonacci Array
long long* generateFibonacci(size_t n)
{
if (n == 0)
return NULL;
long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n; ++i)
{
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray;
}
This requires O(N) additional memory to store the Fibonacci sequence.
Recursive Factorial
long long factorial(int N)
{
if (N == 0)
return 1;
return factorial(N - 1) * N;
}
Recursive functions consume O(N) space due to the call stack depth.
Algorithm Practice Problems
Missing Number Problem
Given an array containing n distinct numbers from 0 to n, find the one that's missing.
Solution Approach
-
Sum formula method:
int findMissing(int* nums, int size){ int total = ((0 + size) * (size + 1)) / 2; for(int i = 0; i < size; i++){ total -= nums[i]; } return total; } -
XOR approach:
int findMissing(int* nums, int size){ int xorResult = 0; for(int i = 0; i < size; i++){ xorResult ^= nums[i]; } for(int i = 0; i <= size; i++){ xorResult ^= i; } return xorResult; }
Both solutions achieve O(N) time complexity.
Rotate Array Problem
Given an array, rotate it to the right by k positions.
Optimized Solution
void reverse(int* arr, int left, int right) {
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
void rotateArray(int* nums, int size, int k) {
k %= size;
reverse(nums, 0, size - k - 1);
reverse(nums, size - k, size - 1);
reverse(nums, 0, size - 1);
}
This solution operates in O(N) time and O(1) space.