Linux Kernel Development (Second Edition) [Electronic resources] نسخه متنی

اینجــــا یک کتابخانه دیجیتالی است

با بیش از 100000 منبع الکترونیکی رایگان به زبان فارسی ، عربی و انگلیسی

Linux Kernel Development (Second Edition) [Electronic resources] - نسخه متنی

Robert Love

| نمايش فراداده ، افزودن یک نقد و بررسی
افزودن به کتابخانه شخصی
ارسال به دوستان
جستجو در متن کتاب
بیشتر
تنظیمات قلم

فونت

اندازه قلم

+ - پیش فرض

حالت نمایش

روز نیمروز شب
جستجو در لغت نامه
بیشتر
لیست موضوعات
توضیحات
افزودن یادداشت جدید






Putting It All Together


Consider the original example of having to count the number of people in a room. Pretend you can count one person per second. Then, if there are seven people in the room, it will take seven seconds to count them. More generally, given n people it will take n seconds to count everyone. Thus, you can say this algorithm is O(n). What if the task was to dance in front of everyone in the room? Because it would take the same amount of time to dance whether there were five or five thousand people in the room, this task is O(1). See Table C.1 for other common complexities.

Table C.1. Table of Common Time Complexity Values

O(g(x)) Name
1 constant (perfect scalability)
log n logarithmic
n linear
n2 quadratic
n3 cubic
2n exponential (evil)
n! factorial (pure evil)

What is the complexity of introducing everyone in the room to everyone else? What is a possible function that models this algorithm? If it took thirty seconds to introduce each person, how long would it take to introduce 10 people to each other? What about one hundred people to each other?

/ 215