What does it mean to say that the height of a complete binary tree is O(log n)? Many good answers have already been posted to this question, but I believe we really are missing an important one - namely, the illustrated answer. Every time the robot goes to load an original book, the factory printer makes a duplicate run of all the phonebooks! Fortunately, the robot's bug-detection systems are sophisticated enough that the robot doesn't try printing even more copies when it encounters a duplicate book for loading, but it still has to load every original and duplicate book that's been printed. The next day, one of your co-workers plays a prank on you and wires the loading dock robot to the automated printing systems. O(n n): You fix the robot so that it's loading things correctly. Unfortunately, the robot that was supposed to load the books has gone haywire: it's putting the books onto the truck in a random order! Even worse, it loads all the books onto the truck, then checks to see if they're in the right order, and if not, it unloads them and starts over. n!): We're ready to load the phonebooks onto the shipping dock.Take some white-out and remove each zero. O(n 2): A mistake occurred at the office, and every entry in each of the phone books has an extra "0" at the end of the phone number. O(n log n): We want to personalize the phone book, so we're going to find each person or business's name in their designated copy, then circle their name in the book and write a short thank-you note for their patronage. Every person or business gets one phone book. Phone books are waiting to be mailed to each resident or business, and there's a sticker on each phone book identifying where it should be mailed to. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.įor the below examples, we're now at the printer's office. O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. O(n): Given a phone number, find the person or business with that number. O(n): Find all people whose phone numbers contain the digit "5". (This is a binary search for a person's name.) Then repeat the process about halfway through the part of the book where the person's name lies. O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. O(1) (in the average case): Given the page that a person's name is on and their name, find the phone number. O(1) (in the worst case): Given the page that a business's name is on and the business name, find the phone number. Here are the running times of some operations we might perform on the phone book, from fastest to slowest: We will also assume that it takes constant time to flip to a specific page. A phone number is assigned to at most one person or business. We will assume our phone book has businesses (the "Yellow Pages") which have unique names and people (the "White Pages") which may not have unique names. We can expand the phone book example to compare other kinds of operations and their running time. Of course, a bigger phone book will still take you a longer time, but it won't grow as quickly as the proportional increase in the additional size. You don't need to check every person in the phone book to find the right one instead, you can simply divide-and-conquer by looking based on where their name is alphabetically, and in every section you only need to explore a subset of each section before you eventually find someone's phone number. This is why, for example, looking up people in a phone book is O(log n). the elements on which the action is performed are digits of n.the choice of the next element on which to perform some action is one of several possibilities, and.The most common attributes of logarithmic running-time function are that: I cannot understand how to identify a function with a log time.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |