Introduction to Algorithms No.5

Hello. Long time not to see. I enjoyed summer vacation...

This is the merge-sort algorithm:

https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/merge_sort.c


Merge-sort is one of divide-and-conquer algorithms. It may be important to understand the concept. Let me explain it.
Divide means cutting a problem into some small ones. Conquer means solving the divided problems. Then we combine the divided problems and we solve the entire problem. In merge-sort, divide is:
<1 2 8 7 6 3 5 4>   --->   <1 2 8 7> <6 3 5 4>
 Conquer is:
<1 2 8 7> <6 3 5 4>   --->   <1 2 7 8> <3 4 5 6>
Combine is:
<1 2 7 8> <3 4 5 6>   --->   <1 2 3 4 5 6 7 8>
Now let T(n) be the running time of sorting a n-size array. Then, we have the following recursion:
T(n) = c, (if n = 1), 2T(n/2) + O(n), (if n > 1).
(2T(n/2) is the running time of conquer. O(n) is the running time of combine here.)

In conclusion, we can get a recursion from a divide-conquer algorithm. And we can calculate the running time.


Thank you. See you tomorrow.
 

Comments

Post a Comment

Popular posts from this blog

Introduction to Algorithms No.3

Hello. I would have completed Chapter 2. But I have not. It takes a lot of time to think about and write algorithms. These are what I have finished writing today: https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/searching_problem.c https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/add_two_n-bit_integers.c The first program is about a searching problem. It receives an array and a number that the array has, as an input. Like (5, 3, 4, 2, 1), 4. Then it returns where the number is, as an output, 3. The second program is about adding two n-bit integers. It receives two n-bit integers as an input. Like (11010), (11100). Then it returns the sum of those integers as an output. Like (110110). In addition, I have learnt "loop invariant." I would like to tell you here. But it is difficult to explain. I will show you it some other time :( Thank you.
Read more

Introduction to Algorithms No.2

Hello. Today, I have learnt "Insertion-Sort Algorithm" in Chapter 2, "Getting Started." I have written a C program of the insertion-sort algorithm. And I have learnt how to use Git and GitHub. So I can show you this C program in GitHub. https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/insertion_sort.c I have not read all of Chapter 2 yet, because I have learnt GitHub today. But I will complete Chapter 2 tomorrow. Thank you.
Read more

Introduction to Algorithms No.1

I have decided to read " Introduction to Algorithms ." This is one of the most famous textbook on algorithms. I will write what I think when I read it. Today, I will write an article on Chapter 1 Chapter 1 refers to "The Role of Algorithms in Computing." The points are as follows: - An algorithm receives an input and returns an output. - Algorithms play an important role in information technology. - A good algorithm on a bad computer may exceed a bad algorithm on a good computer. Good algorithms are as important as a good computer! Thank you.
Read more