Welcome!
I am an first-year computer science major master student at the University of Southern California
Dynamic Programming Revisit
The core of dynamic programming: recursion with memorization. Breaking a big problem into small sub-problems and only computing each sub-problem once. Notice dynamic programming is an algorithm that will essentially search the entire solution space It’s usually helpful to think what’s the last step in your solution (top-down) and what sub-problem will it generate. But … Continue reading “Dynamic Programming Revisit”
Full Analysis of Finding K Smallest in Sorted/Unsorted Arrays
Problem Statement: Giving m unsorted arrays, return the k smallest elements Method #1: Min-heap Method 1: Using bottom-up heap construction to build a min-heap, then pop the smallest element n times Complexity analysis: Time to construct min-heap: O(n) Time to extract min k times: O(k * lgn) Total time complexity: O(n + k * lgn) … Continue reading “Full Analysis of Finding K Smallest in Sorted/Unsorted Arrays”
Follow My Blog
Get new content delivered directly to your inbox.
kaiwang.co 