Introducing the greedy algorithm

I, Introduction to greedy algorithm

In this article, I will introduce an interesting type of algorithm called the greedy algorithm. The solution of this type of algorithm is to always choose the best solution at the current time. This locally optimal solution is in the hope that the result on the global level will be optimized (globally-optimal solution).

II, Advantages and disadvantages

The greedy algorithm has several advantages and disadvantages as follows:

Advantage:

Easy to come up with solutions with greedy algorithmic approach Easy to analyze space and time complexity compared to other techniques (like Divide and Conquer approach)

Disadvantages:

Proving the correctness of an algorithm is more difficult than other techniques.

Example Problem 1 - Tandem Bicycle

Problem: A tandem bicycle is ridden by two riders wearing red and blue shirts. Both riders are pedaling but the speed of the bicycle is equal to the speed of the faster rider. The input is two lists containing the speeds of the riders wearing red and blue shirts. Return the sum of the highest speeds of the pairs of bikers.

Input:

Output:

Solution:

During the Warring States period, Sun Tzu, the grandson of Sun Tzu (author of The Art of War by Sun Tzu), was a brilliant strategist of the Qi state. During Tian Ji's horse race with King Wei, Sun Tzu gave Tian Ji the following brilliant plan:

The solution to this problem is similar to the above: We pair the fastest runners (highest horses) on one team with the slowest runners (lowest horses) on the other team. Since the speed of the bike is equal to the speed of the fastest cyclist, the total speed of the pairs will be the largest. The detailed solution is as follows:

1. Sort one list; sort the other list in reverse order.
2. Zip sorted list creates pairs consisting of one member in blue shirt and one member in red shirt.
3. Calculate the speed of the cars in the pair using the formula max(red_speed, blue_speed).
4. Calculate the sum of the speeds of the pairs.

My Python solution:

Space and time complexity analysis

Note: n is the number of input elements

Space complexity is O(1)

1. Since the entire algorithm processes the two input lists themselves, the space complexity is constant - O(1)

Time complexity is O(nlogn)

1. Time complexity to sort 2 lists is O(nlogn) Time complexity to calculate speed of pairs will be O(n) Therefore total time complexity is O(nlogn)

Note: the log factor in Computer Science defaults to 2, not 10.

Example Problem 2 - Minimum Waiting Time

Problem: Take a list of positive integers representing the time required to perform a task. Only one task can be performed at a time. The waiting time is the time required to wait before performing the next task. For example, if the task is performed second, the waiting time is the time required to perform the first task. Write a function that returns the lowest number of waiting times received for all input tasks.

Input:

Output:

Solution:

To optimize the lowest waiting time, we will take advantage of the time of the job that is closer to the end, the less impact it has. Therefore, we will put the jobs with the longest execution time at the end. The solution is described as follows:

algorithm illustration

Detailed solution:

1. First we sort the input list
2. We can see that the waiting time example above is the time it takes to perform a task that appears in the waiting time of the following tasks. That means the total waiting time will include (length - i) * n (where length is the length of the list, i is the current index and n is the time it takes to perform the current task)
3. Therefore we will use the generalized formula above to calculate the minimum waiting time.

The solution is as follows:

Space and time complexity analysis:

Space complexity is O(1)

Since we are processing on the input list itself, the space complexity is constant - O(1)

Time complexity is O(nlogn)

1. Time complexity to sort list is O(nlogn)
2. Time complexity to iterate through the list to calculate waiting time is O(n)
3. Therefore the total complexity is O(nlogn)

Conclude

Hopefully, this article has given you an overview of the greedy algorithm. If you find this blog interesting, please share it so that more people can know about it. And look forward to more of my blog posts on the topic of Data Structure & Algorithm on TipsMake's tech blog!