Welcome!
I am an first-year computer science major master student at the University of Southern California
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
Dynamic Programming
Introduction Dynamic programming is closely related to divide & conquer and has far-ranging applications. They share the same idea of dividing a bigger and complicated question into smaller and easy-to-solve sub-problems of the same type. So both of them are based on recursion. The difference: In divide & conquer, sub-problems share the same type with … Continue reading Dynamic Programming
Divide & Conquer
Introduction Divide and conquer is a basic but powerful technique that is widely used in many algorithms. As you might speculate from its name, the principle of divide and conquer is to recursively divide a complicated problem into a few simple sub-problems of the same type (divide), until they become simple enough and we can … Continue reading Divide & Conquer
Follow My Blog
Get new content delivered directly to your inbox.
