Introduction to Algorithms No.7

Hello. Today, I have started Chapter 4, "Divide and Conquer." And I have learnt "The maximum-subarray problem."

Maximum-subarray algorithm can solve that problem. Suppose you have time series of stock prices, such as (5 10 4 2 3 7 1 5 6 2). You are at time 1 now. The stock price is 5 now. You know the future stock price (5 10 4 2 3 8 1 3 6 2). Then when will you buy the stock and sell it? The answer is, you should buy it at time 4 and sell it at time 6. Then you get 6.

I have written two codes, which run with different running time. One algorithm runs with Theta(n^2). The other runs with Theta(n*log(n)). Therefore, the latter runs faster. The two algorithms are as follows:

https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/maximum-subarray_problem_slow.c

https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/maximum-subarray_problem_fast.c

You will be surprised to recognize that the slow program is much simpler and shorter than the fast program!


The fast one is one of divide-conquer algorithms, which I have recently explained.

Calculating the running time needs mathematical analysis.


Thank you.


MEMO
Big O-notation determines the upper bound of the running time. Omega-notation determines the lower bound. Theta-notation determines the both.

Small o-notation of a function includes all functions that runs faster than the function for enough large n. If you find an algorithm that runs at Theta(f(n)), then you should find another algorithm that runs at o(f(n)).

Comments

  1. KeroAug 16, 2018, 8:15:00 AM

    If I can know the price of the stock early, I will consider using your algorithm($_$). Unfortunately, I don't know much about the second algorithm, because the syntax of the c language is different from java. You are writing very well, I hope you have the time to teach me some c language.(this comment is translated by google translation from chinese to English)

    ReplyDelete

Post a Comment

Popular posts from this blog

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

Introduction to Algorithms No.10

Hello. I have learnt introduction in "II Sorting and Order Statistics." Sorting algorithms and order statistics really matters in computer engineering, which encourages me to learn algorithms. The sorting algorithms have heap-sort, quick-sort, counting-sort, radix-sort, and bucket-sort. The order statistics means searching the n-th smallest number in a array. Tomorrow, I will tell you heap-sort. Thank you.
Read more

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 concl
Read more