Brute force-algorithm

Brute force-algorithm

• 1.
  BRUTE-FORCE-ALGORITHM
• 2.
  INTRODUCTION The Maximum sub-arrayproblem is the task of finding the contiguous sub-array within a one dimensional array. For Example: Brute force algorithm is a step by step procedure for solving a problem so it is consider as a straight forward approach usually based on the problem statement. 1 -3 2 -5 7 6 -1 -4 11 -23 0 1 2 3 4 5 6 7 8 9
• 3.
  PSEUDO CODE Max-Sub-array-Brute-Force (A) n= A.length max-so-far = -∞ For l = 1 to n sum = 0 for h = l to n sum = sum + A[h] if sum > max-so-far max-so-far = sum low = l high = h Return (low , high)
• 4.
  IMPLEMENTATION 3 -2 5-1 0 1 2 3 FOR EXAMPLE : 1. 3 SUM: -2 5 -1 3 -2 -15 MAX_SO_FA R 3 3 5 5 2. 3 -2 -2 5 5 -1 SUM: 1 MAX_SO_FA R 5 3 5 5 4 Taking one at a time : Taking two at a time :
• 5.
  3. 3 -2 -25 SUM: 6 MAX_SO_FA R 6 2 6 Taking three at a time : IMPLEMENTATION 5 -1 3 -2 SUM: 5 MAX_SO_FA R 6 5 4. Taking four at a time : -1
• 6.
  IMPLEMENTATION 3 -2 5-1 0 1 2 3 Maximum Sub-Array
• 7.
  Max-Sub-array-Brute-Force (A) n =A.length max-so-far = -∞ For l = 1 to n sum = 0 for h = l to n sum = sum + A[h] if sum > max-so-far max-so-far = sum low = l high = h Return (low , high) O(n) O(n) Time Time Complexity Overall time complexity : O(n2)
• 8.
  CONCLUSION  Brute forceis a straight forward approach to problem solving , It is applicable to very wide variety of problem.  Brute force algorithm is useful for solving small size instance of problem.  A brute force algorithm can serve an important theoretical or educational purpose.  A brute force algorithm is often easier to implement than a more sophisticated one and , because of this simplicity, sometime it can be more efficient.  Brute force algorithm is used when the simplicity of implementation is more important than speed.  Brute force algorithm can be applied only to problems where input size is small , otherwise it will be not efficient .