Source code online books for professionals by professionals


Forgetting. Of course, the assert doesn’t work. ( http://xkcd.com/379 ) Note



Download 4,67 Mb.
Pdf ko'rish
bet15/266
Sana31.12.2021
Hajmi4,67 Mb.
#213682
1   ...   11   12   13   14   15   16   17   18   ...   266
Bog'liq
2 5296731884800181221

Forgetting. Of course, the assert doesn’t work. (
http://xkcd.com/379
)
Note
 

  exactly how you encode your problems and solutions as bit patterns usually has little effect on the asymptotic 
running time, as long as you are reasonable. For example, avoid representing your numbers in the unary number system 
(1=1, 2=11, 3=111…).
The asymptotic notation consists of a bunch of operators, written as Greek letters. The most important ones,  
and the only ones we’ll be using, are O (originally an omicron but now usually called “Big Oh”), W (omega), and  
Q (theta). The definition for the O operator can be used as a foundation for the other two. The expression O(g), for 
some function g(n), represents a set of functions, and a function f(n) is in this set if it satisfies the following condition: 
There exists a natural number n
0
 and a positive constant c such that
f(n) £ cg(n)
for all n ³ n
0
. In other words, if we’re allowed to tweak the constant c (for example, by running the algorithms on 
machines of different speeds), the function g will eventually (that is, at n
0
) grow bigger than f. See Figure 
2-1
 for an 
example.


Chapter 2 

 the BasiCs
13
This is a fairly straightforward and understandable definition, although it may seem a bit foreign at first. Basically, 
O(g) is the set of functions that do not grow faster than g. For example, the function n
2
 is in the set O(n
2
), or, in set 
notation, n
2
 
∈ O(n
2
). We often simply say that n
2
 is O(n
2
).
The fact that n
2
 does not grow faster than itself is not particularly interesting. More useful, perhaps, is the fact that 
neither 2.4n
2
 + 7 nor the linear function n does. That is, we have both
2.4n
2
 + 7 ∈ O(n
2
)
and
n 
∈ O(n
2
).
The first example shows us that we are now able to represent a function without all its bells and whistles; we can 
drop the 2.4 and the 7 and simply express the function as O(n
2
), which gives us just the information we need. The 
second shows us that O can be used to express loose limits as well: Any function that is better (that is, doesn’t grow 
faster) than g can be found in O(g).
How does this relate to our original example? Well, the thing is, even though we can’t be sure of the details 
(after all, they depend on both the Python version and the hardware you’re using), we can describe the operations 
asymptotically: The running time of appending n numbers to a Python list is O(n), while inserting n numbers at its 
beginning is O(n
2
).
The other two, W and Q, are just variations of O. W is its complete opposite: A function f is in W(g) if it satisfies the 
following condition: There exists a natural number n
0
 and a positive constant c such that
f(n) ³ cg(n)
for all n ³ n
0
. So, where O forms a so-called asymptotic upper bound, W forms an asymptotic lower bound.
Note
 

  Our first two asymptotic operators, O and 
W, are each other’s inverses: if f is O(g), then g is W(). exercise 2-3 
asks you to show this.
The sets formed by Q are simply intersections of the other two, that is, Q(g) = O(g
∩ W(g). In other words, a function f is 
in Q(g) if it satisfies the following condition: There exists a natural number n
0
 and two positive constants c
1
 and c
2
 such that
c
1
g(n) £ f(n) £ c
2
g(n)
for all n ³ n
0
. This means that f and g have the same asymptotic growth. For example, 3n
2
 + 2 is Q(n
2
), but we could just 
as well write that n
2
 is Q(3n
2
 + 2). By supplying an upper bound and a lower bound at the same time, the Q operator is 
the most informative of the three, and I will use it when possible.
cn 

Download 4,67 Mb.

Do'stlaringiz bilan baham:
1   ...   11   12   13   14   15   16   17   18   ...   266




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish