반응형
Problem
4.1 Trival
Algorithm Illustration
Pseudo-code
1 function T(n)
2 if n <= 1 then
3 return 1
4 else
5 c = ceil(n / 2)
6 return T(n - 1) +T(c) + n
7 end if
8 end function
C++ code
#include <iostream>
#include <cmath>
using namespace std;
// Trivial recursive algorithm for T(n) = T(n-1) + T( ceil ( n / 2) ) + n
int T(int n) {
// Base case
if (n <= 1) {
return 1;
}
else {
// Recursive case
int c = ceil(n / 2);
return T(n-1) + T(c) + n;
}
}
int main() {
int n;
cout << "Enter the value of n: ";
cin >> n;
int result = T(n);
cout << "T(" << n << ") = " << result << endl;
return 0;
}
🌟 The best-case scenario for this algorithm occurs when the function reaches its base case with a time complexity of O(1).
🌟 In the worst-case, the time complexity is O(2^n) due to the exponential growth in the number of function calls.
🌟The algorithm becomes significantly slower as n increases due to the repetitive calculation of the same subproblems.
- the best case: O(1), when the function hits its base case, when n <= 1. In this case, the function returns immediately with a constant time operation, O(1).
- the worst and overall case: O(2^n), where n is the input size. This is because each function call to T(n) generates two more calls for each non-base case, leading to an exponential growth in the number of function calls.
4.2 Dynamic Programming
Algorithm Illustration
Pseudo-code
1: function T(n)
2: if n <= 1 then
3: return 1
4: end if
5:
6: if memo[n] is not -1 then
7: return memo[n]
8: end if
9:
10: c = ceil(n / 2)
11: memo[n] = T(n - 1) + T(c) + n
12:
13: return memo[n]
14: end function
- [Pseudo-Code] Line 1-4: the complexity is O(1)
- The algorithm starts by checking if n <= 1, the function returns 1. This is a constant-time operation which means O(1).
- Line 6-8: the complexity is O(1) / Memoization check
- Before computing T(n), the algorithm checks if the value has already been computed and stored in memo[n]. If memo[n] is not -1, it returns the stored value.
- This is also a constant-time operation, O(1).
- Line 10-11: the complexity is O(n) Dynamic programming
- The T(n - 1) call will compute all values of T from n-1 down to 1 if they haven't been computed before.
- For the T(c) call, since c is approximately n/2, each call will process a number that is half of the current n.
C++ code
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
vector<int> memo; // Global memorization array
// Dynamic programming algorithm for T(n) = T(n-1) + T( ceil(n/2) ) + n
int T(int n) {
if (n <= 1) {
return 1;
}
if (memo[n] != -1) {
return memo[n];
}
int c = ceil(n / 2);
memo[n] = T(n - 1) + T(c) + n;
return memo[n];
}
int main() {
int n;
cout << "Enter the value of n: ";
cin >> n;
// Initialize the memoization array with -1
memo.resize(n + 1, -1);
int result = T(n);
cout << "T(" << n << ") = " << result << endl;
return 0;
}
🌟 The best-case scenario has a time complexity of O(1) when n is less than or equal to 1.
🌟The worst-case scenario, with memoization, has a time complexity of O(n) due to each unique call being computed only once.
🌟 The overall complexity is O(n) in the worst case.
- the best case: O(1), when n is less or equal to 1, then the time complexity becomes O(1). This is because no recursive calls or computations will be needed since the algorithm will immediately return 1.
- the worst and overall case: O(n), the memoization ensures that each unique call to T(n) is computed only once. After a value is computed, it's stored in memo[n], and any subsequent calls for the same n will return the pre-computed value, leading to a linear time complexity O(n) in the worst case.
Conclusion
The difference is shown when the vector size gets larger, the trivial recursive approach takes an increasingly longer time to calculate than the dynamic programming approach; which has a gradual increase in time required as n becomes larger.
반응형
댓글