Skip to main content
Definition Website Computer and Technology

Greedy Algorithm

Subject: Computer and Technology noun /ˈɡriː.di ˈæl.ɡəˌrɪð.əm/ 1 definition

  1. Definition (noun)

    Entry #58 · Updated

    A Greedy Algorithm is an algorithmic design paradigm that builds a solution incrementally by selecting the locally optimal choice available at each decision point without reconsidering earlier choices. By committing immediately to the best immediate option rather than exploring multiple branches as in dynamic programming or backtracking, it achieves low time and memory overhead. However, a greedy approach guarantees a globally optimal solution only when the problem exhibits both the greedy choice property and optimal substructure; otherwise, it serves as a fast heuristic that can yield a suboptimal result.

    Common Types

    • Selection and Scheduling Algorithms: Process candidates in sorted order of a single metric—such as earliest finish time in interval scheduling or value-to-weight ratio in the fractional knapsack problem—to maximize throughput or utility in a single pass.

    • Graph and Spanning-Tree Algorithms: Construct optimal paths or trees edge by edge or vertex by vertex by picking the lowest-cost valid addition, as seen in Kruskal's and Prim's minimum spanning tree algorithms and Dijkstra's shortest-path algorithm for non-negative weights.

    • Prefix-Coding Algorithms: Build minimal-redundancy binary trees by repeatedly combining the two lowest-frequency symbols, forming the basis of lossless data compression schemes such as Huffman coding.

    • Approximation Heuristics: Provide fast, bounded near-optimal solutions for NP-hard problems—including set cover, bin packing, and nearest-neighbor routing—where finding an exact optimum requires prohibitive computational time.

    Example

    A cloud job scheduler receives a queue of six non-preemptive tasks with overlapping runtime windows to execute on a single worker node. Applying a greedy interval-scheduling strategy, it sorts the tasks by earliest finish time—starting with a task ending at 10:15, then selecting the next compatible task finishing at 10:40, and continuing sequentially—to schedule the maximum number of tasks in O(n log n) time without evaluating every subset.