rag/knowledge_base/greedy_algorithms_overview.txt

TOPIC: Greedy Algorithms Overview

DEFINITION: 
Greedy algorithms are a type of algorithmic strategy that solves problems by making the locally optimal choice at each step, with the hope that these local choices will lead to a globally optimal solution. This approach is useful for solving optimization problems, where the goal is to find the best solution among a set of possible solutions. By choosing the best option at each step, greedy algorithms aim to find a solution that is optimal or close to optimal.

TIME_COMPLEXITY: 
The time complexity of greedy algorithms can vary depending on the specific problem, but it is often O(n), where n is the number of elements being processed, because the algorithm typically makes a single pass through the data.

SPACE_COMPLEXITY: 
The space complexity of greedy algorithms is usually O(1), because the algorithm only needs to keep track of a limited amount of information, such as the current solution and any relevant parameters.

USE_WHEN: 
Greedy algorithms are a good choice when the problem has the following properties: the problem can be broken down into smaller sub-problems, and the optimal solution to the larger problem can be constructed from the optimal solutions of the sub-problems. This is often the case in problems that involve finding the shortest path, the minimum spanning tree, or the optimal scheduling.

AVOID_WHEN: 
Greedy algorithms are not the best choice when the problem requires considering the global optimality, and the locally optimal choices do not necessarily lead to a globally optimal solution. In such cases, other algorithms like dynamic programming may be more suitable.

EXAMPLE: 
Consider a problem where we need to make change for 6 units using coins of denominations 1, 2, and 5. 
  Start with 6 units
  -> subtract 5 ( largest possible coin) = 1 unit left
  -> subtract 1 ( largest possible coin) = 0 units left
  Result: [5, 1] 
  Checkmark: The greedy algorithm finds a valid solution by making the locally optimal choice at each step.

REAL_WORLD_ANALOGY: 
The greedy algorithm is similar to a person trying to make change for a purchase, where they try to use the largest denomination bills and coins first to minimize the total number of items used.

SOURCE_NOTE: 
Concepts referenced from general knowledge of algorithms and data structures, synthesized for clarity and conciseness.