Sponsored
Sponsored
This approach involves breaking down the problem into smaller subproblems, solving each subproblem recursively, and then combining the results. This is a classic Divide and Conquer approach which can be applied to a variety of problems, such as sorting algorithms (e.g., Merge Sort).
Time Complexity: O(n log n)
Space Complexity: O(n)
1function merge(arr, left, mid, right) {
2 const n1 = mid - left + 1;
3 const n2 = right - mid;
4 const L = new Array(n1);
5 const R = new Array(n2);
6
7 for (let i = 0; i < n1; i++)
8 L[i] = arr[left + i];
9 for (let j = 0; j < n2; j++)
10 R[j] = arr[mid + 1 + j];
11
12 let i = 0, j = 0, k = left;
13 while (i < n1 && j < n2) {
14 if (L[i] <= R[j]) {
15 arr[k] = L[i];
16 i++;
17 } else {
18 arr[k] = R[j];
19 j++;
20 }
21 k++;
22 }
23
24 while (i < n1) {
25 arr[k] = L[i];
26 i++;
27 k++;
28 }
29
30 while (j < n2) {
31 arr[k] = R[j];
32 j++;
33 k++;
34 }
35}
36
37function mergeSort(arr, left, right) {
38 if (left < right) {
39 const mid = left + Math.floor((right - left) / 2);
40
41 mergeSort(arr, left, mid);
42 mergeSort(arr, mid + 1, right);
43
44 merge(arr, left, mid, right);
45 }
46}
47
48let arr = [12, 11, 13, 5, 6, 7];
49mergeSort(arr, 0, arr.length - 1);
50console.log("Sorted array:", arr);This JavaScript code provides a Merge Sort implementation. It makes use of the merge function to merge two sorted parts of an array and applies recursion in the mergeSort function to divide the array into smaller parts.
Dynamic Programming (DP) is an approach that solves complex problems by breaking them down into simpler subproblems and storing the results to avoid recomputing. It's particularly useful for optimization problems where decisions depend on previous decisions.
Time Complexity: O(n)
Space Complexity: O(n)
1using System;
class Fibonacci {
int Fib(int n, int[] dp) {
if (n <= 1) return n;
if (dp[n] != -1) return dp[n];
return dp[n] = Fib(n-1, dp) + Fib(n-2, dp);
}
public static void Main(string[] args) {
int n = 10;
int[] dp = new int[n + 1];
Array.Fill(dp, -1);
Fibonacci fibonacci = new Fibonacci();
Console.WriteLine("Fibonacci number is " + fibonacci.Fib(n, dp));
}
}This C# code is a dynamic programming solution for computing Fibonacci numbers. It uses a memoization technique with an integer array to optimize the recursive calls, ensuring that each subproblem is solved only once.