[CS] Greedy Algorithm / Implementation Day-72

Life is C(Choice) between B(Birth) and D(Death)

What is Algorithm?

It is the best choice to solve the problem.

Time Complexity

It is important to find the correct answer to a problem, but it is also important to solve the problem in an efficient method.

Finding an efficient method is one of the ways to solve time complexity.

Big-O?

How to express time complexity.

• Big-O
• Big-Ω
• Big-θ

The above three notations tell us whether it is the best or the worst.

O(n) === 'linear complexity'

As the input increases, time also increases at the same rate.
If you input double value, Time takes twice as long.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

O(log n) === 'logarithmic complexity'

Binary Search Tree is example of logarithmic complexity. Each time to move a Node, Time to find results is cut in half.

let i = n;
while (parseInt(i) > 0) {
  i = i / 2;
}

ex) O(log k n) or O(log n)

for (let i = 0; i < n; i++) {
	i *= k;
}

O(n^2) === 'quadratic complexity'

As the input increases, the time increases as a power of n.

• n^2, n^3, n^5 is all same cases

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

O(2^n) === 'exponential complexity'

This is the case with the slowest time complexity. need to find another efficient way.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

O(log n) is not always faster than O(n)
As n gets bigger, O(log n) gets faster. If n is 1, the speed is the same.

Greedy Algorithm

• Selection Procedure: Choose the best solution in the current state
• Feasibility Check: Check the selected method satisfies the condition of the problem
• Solution Check: Check the problem is solved, and if it's not, return to the Selection Procedure.

Greedy Algorithm is problem-solving method that always finds the optimal solution. However, it does not always guarantee optimal results.

Implementation

Must know exactly the grammar of the programming language you have chosen, and the goal is to quickly write code that meets all the conditions of the problem without mistakes.

Coding requires concentration and persistence.

brute force

All problems can be solved with brute force. It's a simple method, but you can always find the answer. But it's not efficient method.

simulation

Thinking about how to solve a problem can be easy, but writing code is hard.

If you omit even one condition, it's not easy to find the correct answer.