[Powered by Google Translate] Siz yəqin ki, insanların sürətli və ya səmərəli alqoritm haqqında danışmaq duydum
xüsusi tapşırığı yerinə ki,
lakin bu sürətli və ya səmərəli olması üçün alqoritm üçün dəqiq nə deməkdir?
Bəli, bu, real vaxt bir ölçü söhbət deyil
saniyə və ya dəqiqə kimi.
Çünki kompüter hardware
və proqram kəskin dəyişir.
Mənim proqram, sizin ləng run bilər
Mən köhnə kompüter üzrə çalışan alıram çünki
və ya bir online video oyun oynayan üçün baş, çünki
eyni zamanda, bu, bütün yaddaş hogging olunur
və ya müxtəlif proqram vasitəsilə mənim proqram çalışan bilər
bir aşağı səviyyədə fərqli maşın ilə əlaqələndirir.
Bu alma və portağal müqayisə kimi.
Mənim yavaş kompüter uzun çəkir Məhz
sizin cavab geri vermək çox
Siz daha səmərəli alqoritm var demək deyil.
>> Belə ki, biz birbaşa proqramları runtimes müqayisə bilməz ildən
saniyə və ya dəqiqə,
necə 2 müxtəlif alqoritmləri müqayisə yoxdur
asılı olmayaraq, hardware və ya proqram ətraf mühit?
Alqoritmik səmərəliliyinin qiymətləndirilməsi bir daha forma yol yaratmaq üçün
kompüter alim və riyaziyyatçılar devised var
bir proqram asimptotik mürəkkəblik ölçülməsi üçün anlayışlar
və notation 'Big Ohnotation "adlı
Bu təsvir.
Rəsmi definition bir funksiyası f (x)
g sifarişi (x) çalışır
bəzi (x) dəyəri var, əgər x ₀ və
bəzi daimi, C, üçün
f (x)-dən az və ya bərabər
ki, daimi dəfə g (x)
x ₀ daha bütün x.
>> Amma formal tərifi ilə üz qorxuram olmayın.
Bu, həqiqətən, nəzəri baxımından az nə deməkdir?
Bəli, bu əsasən təhlil yolu var
bir proqramın iş asimptotik artır necə sürətli.
Sizin vəsaitlərin həcmi sonsuzluğa doğru artır ki, edir
söz, siz ölçüsü 10 bir sıra müqayisədə ölçüsü 1000 bir sıra çeşidlənməsi edirik.
Sizin proqram iş necə inkişaf edir?
Məsələn, simvol sayını hesablamaq təsəvvür
simli ən sadə yolu
bütün cərgə ilə gəzinti ilə
məktub-by-məktub və hər bir xarakter üçün counter 1 əlavə.
Bu alqoritm Xətti zaman çalışır deyilir
simvolların sayı ilə əlaqədar,
Simli ildə 'n'.
Qısa olaraq, O (n) çalışır.
Niyə bu?
Bəli, bu yanaşma istifadə edərək, zaman tələb
bütün simli axır etmək
simvolların sayını orantılıdır.
20 xarakter string simvol sayı hesablanması
edir kimi iki dəfə kimi uzun gedir
10 xarakter string olan simvol saymaq,
bütün simvol baxmaq, çünki
və hər bir xarakter baxmaq eyni məbləği alır.
Siz simvolların sayını artırmaq kimi,
Runtime giriş uzunluğu xətti artacaq.
>> Əgər xətti vaxt qərar varsa, təsəvvür
O (n), yalnız kifayət qədər sürətli sizin üçün deyil?
Bəlkə, böyük strings saxlanılması edirik
və bunu görəcək əlavə vaxt ödəyə bilməz
bir-bir hesablama onların simvol bütün axır etmək.
Belə ki, fərqli bir cəhd qərar.
Nə artıq simvolların sayını saxlamaq olur əgər
simli ildə, 'len "adlı dəyişən, demək
erkən proqram üzrə,
Siz simli çox ilk xarakter saxlanılır əvvəl?
Sonra bütün siz string uzunluğu tapmaq üçün indi nə etmək istiyorum
dəyişən dəyəri nə kontrol edir.
Siz, bütün simli özü baxmaq olmazdı
və len kimi bir dəyişən dəyəri daxil hesab edilir
bir asimptotik daimi dəfə əməliyyat,
və ya O (1).
Niyə bu? Yaxşı, asimptotik mürəkkəblik nə deməkdir xatırlayıram.
Necə ölçüsü kimi iş dəyişiklik yoxdur
Sizin giriş artır?
>> Bir böyük simli simvol sayı almaq üçün çalışdıqlarını deyirlər.
Bəli, bu, siz string etmək necə böyük məsələ deyil
hətta bir milyon simvol uzun,
bütün bu yanaşma ilə simli uzunluğu tapmaq üçün nə etmək istiyorum
, dəyişən len dəyəri oxuyub üçün
siz artıq təşkil edib.
Ki, daxil uzunluğu tapa çalışdığınız simli uzunluğu,
Proqram çalışır necə sürətli bütün təsir etmir.
Proqram bu hissəsi bir xarakter string haqqında bərabər sürətli çalışır
və min xarakter simli,
Bu proqram sabit zaman çalışır kimi istinad olunacaq niyə və ki
daxil ölçüsü ilə bağlı.
>> Əlbəttə ki, bir günah yoxdur.
Siz kompüter əlavə yaddaş alanı sərf
dəyişən saxlanılması
və sizi əlavə vaxt
dəyişən faktiki storage etmək üçün,
lakin baxımından hələ dayanır,
sizin simli necə uzun tapmaq
bütün simli müddəti asılı deyil.
Belə ki, O (1) və ya daimi zaman çalışır.
Bu, əlbəttə, demək yoxdur
Sizin kodu, 1 addım çalışır
amma nə qədər çox addımlar ki,
bu vəsaitlərin ölçüsü dəyişə deyilsə,
hələ biz O (1) kimi təmsil asimptotik daimi var.
>> Yəqin ki, tapmaq kimi,
ilə alqoritmlər ölçmək üçün bir çox müxtəlif böyük O runtimes var.
O (n) ² alqoritmlər O (n) alqoritmlər çox asimptotik yavaş var.
Elementlərinin sayı (n) artır ki, edir
nəhayət O (n) ² alqoritmləri daha çox vaxt aparacaq
O (n) alqoritmlər çalıştırmak üçün çox.
Bu O (n) alqoritmlər həmişə daha sürətli run demək deyil
O (n) ² alqoritmlərin çox, hətta eyni mühitdə,
Eyni hardware.
Bəlkə kiçik giriş ölçüləri üçün,
O (n) ² alqoritm əslində, daha sürətli iş bilər
amma, nəhayət, giriş ölçüsü artırır
sonsuzluğa doğru, O (n) ² alqoritm nin iş
nəticədə O (n) alqoritmi Runtime geridə qoya edəcək.
Hər hansı bir kvadrat riyazi funksiyası kimi
nəticədə hər linear function keçəcəyi təxmin edilir,
nə qədər baş linear function başlamaq heç bir məsələ ilə off başlayır.
Siz məlumatın böyük həcmdə iş edirsinizsə
O çalışır ki, alqoritmlər (n) ² zaman, həqiqətən, proqram yavaşlatan başa bilər
lakin kiçik giriş ölçüləri üçün,
yəqin ki, qeyd belə deyil.
>> Digər asimptotik mürəkkəblik edir
logarithmic zaman, O (Giriş n).
Tez bu çalışır ki, bir alqoritm nümunəsi
, klassik ikili axtarış alqoritm edir
elementlərinin artıq sıralaması siyahısında bir element tapmaq üçün.
>> Siz ikili axtarış nə bilmirsinizsə,
Mən, həqiqətən, tez sizin üçün izah edəcəyik.
Deyək ki sayı 3 aradığınız demək
integers bu sıra.
Bu serialın orta element baxır
və "Mən daha çox istədiyiniz element deyil, bərabər və ya bu az?" soruşur,
O böyük, bərabər varsa. Siz element aşkar və siz tamamlayın.
Daha çox varsa, onda siz element bilirik
, serialın sağ tərəfində olmalıdır
və yalnız gələcəkdə baxmaq olar
bu kiçik varsa və sonra onu sol tərəfində olmalıdır bilirik.
Bu proses sonra kiçik ölçülü array ilə təkrar olunur
düzgün element aşkar qədər.
>> Bu güclü alqoritmi hər əməliyyat yarısında array ölçüsü azalıb.
Belə ki, ölçüsü 8-sıralanır array bir element tapmaq,
ən çox (₂ 8 daxil)
bu əməliyyatların və ya 3,
orta element yoxlanılması, sonra yarısında array kəsmə, tələb olunacaq
ölçüsü 16 bir sıra (₂ 16 daxil) alır, halbuki
və ya 4 əməliyyatları.
Bu yalnız bir iki dəfə ölçülü array üçün 1 daha əməliyyatı.
Serialın ölçüsü katlama
bu kodu yalnız 1 yığın tərəfindən uzunluğu artır.
Yenə sonra bölünmə, siyahıda orta element yoxlanılması.
Belə ki, o, logarithmic vaxt fəaliyyətə deyilir
O (Giriş n).
Lakin, demək, gözləyin
siyahıda aradığınız element olduğu bu asılı deyil?
Nə əgər baxmaq ilk element sağ olmaq olur?
Sonra o, yalnız, 1 əməliyyat görür
siyahısında nə qədər böyük olursa olsun.
>> Kompüter alimləri daha baxımından niyə Yaxşı, ki
ən yaxşı halda əks etdirən asimptotik mürəkkəbliyi üçün
və ən pis halda bir alqoritm çıxışları.
Daha düzgün, yuxarı və aşağı həddi
Runtime haqqında.
Binar axtarış üçün ən yaxşı halda, bizim element
orada ortasında,
və siz daimi vaxtında almaq
serialın qalan nə qədər böyük olursa olsun.
Bu istifadə rəmzi Ω edir.
Belə ki, bu alqoritm Ω (1) çalışması edir.
Ən yaxşı halda, o, tez element hesab
serialın nə qədər böyük olursa olsun,
amma ən pis halda,
o (Giriş n) split çek çıxış edir
serialın hüququ element tapa bilərsiniz.
Ən pis halda yuxarı həddi artıq bilirəm ki, böyük "O" ilə aid edilir.
Belə ki, O (Giriş n), lakin Ω (1) var.
>> A xətti axtarış, əksinə,
Siz array hər element vasitəsilə gəzmək olan
istədiyiniz tapmaq,
yaxşı Ω (1) edir.
Yenə ilk element istədiyiniz.
Belə ki, serialın nə qədər böyük əhəmiyyətli deyil.
Ən pis halda, serialın son element var.
Belə ki, siz tapmaq üçün array bütün n elementləri vasitəsilə gəzmək üçün
siz 3 axtarır, əgər istəyirəm.
Belə ki, O (n) zaman çalışır
bu sıra elementlərinin sayına mütənasib hissəsi çünki.
>> Istifadə daha bir simvolu Θ edir.
Bu harada ən yaxşı və ən pis halda alqoritmlər təsvir etmək üçün istifadə edilə bilər
eynidir.
Bu əvvəllər danışdı string uzunluğu alqoritmlər olduğu.
Biz əvvəl bir dəyişən bu saxlamaq əgər ki,
biz simli saxlamaq və sonra sabit zaman daxil.
Nə sayı olmayaraq
biz dəyişən saxlanılması edirik, biz baxmaq lazımdır.
Ən yaxşı halda, biz baxmaq
və simli uzunluğu tapa bilərsiniz.
Ω (1) və ya ən yaxşı halda daimi vaxt belə.
Ən pis halda ki,
biz baxmaq və simli uzunluğu tapa bilərsiniz.
Belə ki, O (1) və ya ən pis halda daimi vaxt.
Belə ki, ən yaxşı halda və ən pis hallarda ildən, eyni
bu Θ (1) vaxt run deyilə bilər.
>> Beləliklə, biz kodları səmərəliliyi haqqında səbəbdən yaxşı yolu var
onlar run etmək üçün real dünya vaxt haqqında heç bir şey bilmədən,
ki, kənar amillər çox təsir edir
müxtəlif hardware, proqram, o cümlədən
və ya kodu xüsusiyyətləri.
Həmçinin, bu, bizə nə olacaq haqqında Səbəb imkan verir
zaman giriş artır ölçüsü.
>> Ey (n) ² alqoritmi, çalışan istəyirsinizsə
və ya pis bir O (2 ⁿ) alqoritmi,
ən sürətlə inkişaf edən növlərindən biridir,
həqiqətən azalması qeyd başlamaq lazımdır
siz məlumatın böyük məbləğlər ilə iş başlamaq zaman.
>> Bu asimptotik mürəkkəblik var. Thanks.