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 kommentar(er)
