Pekala, yani, hesaplama karmaşıklığı. Bir uyarı Sadece biraz biz de far-- dalış önce bu muhtemelen arasında olacak En matematik ağır şeyler Biz CS50 hakkında konuşmak. Umarım çok bunaltıcı olmayacak ve biz denemek ve size rehberlik edeceğiz süreç boyunca, ancak adil bir uyarı sadece biraz. Biraz var matematik Burada yer. Pekala, sipariş, böylece yapmak Bizim hesaplama kaynaklarının kullanımı Gerçek --daha dünya o gerçekten algoritmaları anlamak önemlidir ve nasıl verileri işlemek. Biz varsa gerçekten verimli bir algoritma, biz kaynak miktarını en aza indirebilir biz onunla başa çıkmak için kullanılabilir olması. Biz bir algoritma varsa o bir sürü iş almaya gidiyor Gerçekten işlemek için verilerin büyük seti, bu kadar Daha fazla ihtiyaç olacak daha fazla kaynak ve hangi şeyler para, RAM, tüm bu türüdür. 

Yani, edememek bir analiz algoritması, bu araç seti kullanılarak Temel olarak, sorum sorar Bu algoritma ölçeği nasıl yaptığını biz ona daha fazla veri atmak gibi? CS50 olarak, veri miktarını konum ile çalışan oldukça küçük. Genellikle, bizim programlar gidiyor ikinci veya less-- çalıştırmak için Muhtemelen çok daha az Özellikle erken. 

Ama bu fırsatlar bir şirket hakkında düşünmek müşterilerinin milyonlarca yüzlerce. Ve onlar işlemek gerekiyor müşteri verileri. Müşteri sayısı arttıkça onlar var, büyük ve daha büyük olur o gerektirecek gidiyor Daha fazla ve daha fazla kaynak. Daha kaç kaynaklar? Peki, bu nasıl bağlıdır Biz algoritma analiz, Bu araç kutusunda araçları kullanarak. Biz karmaşıklığı hakkında konuşmak Bir algorithm-- hangi bazen olacak Bu zaman olarak ifade duymak karmaşıklığı ya da uzay karmaşıklığı ama biz sadece gidiyoruz complexity-- dönmesini genellikle bahsediyoruz En kötü senaryo. Mutlak kötü kazık Verilen biz ona atma olabilir veri, bu nasıl algoritma gidiyor işlemek veya bu verilerle başa? Biz genellikle en kötü durum çağrı bir algoritma büyük O zamanı. Yani bir algoritma söylenebilir squared n ya n O O çalıştırın. Hakkında ve ne daha Bu bir saniye demek. 

Bazen, ama, biz bakım yapmak en iyi senaryo hakkında. Veri herşey ise istediğimiz olması ve kesinlikle mükemmel oldu ve biz bu mükemmel gönderiyorlardı Bizim algoritma sayesinde veri ayarlayın. Nasıl bu durumda ele alabileceğinizi? Biz bazen bu bakın Büyük Omega, büyük-O tersine, bu yüzden Biz büyük Omega var. En iyi senaryo için büyük-Omega. En kötü durum senaryosu için Büyük-O. Genellikle, biz yaklaşık ne zaman konuşmak bir algoritma karmaşıklığı, Biz bahsediyoruz En kötü durum senaryosu. Yani akılda tutmak. 

Ve bu sınıfta, genellikle gidiyoruz bir kenara titiz analizler bırakmak. Bilimler ve alanlar vardır bu tür şeylerle adamıştır. Biz akıl hakkında konuşmak algoritmalar sayesinde, Biz birçok parça-by-parça yapacağım ki algoritmalar Sınıfta hakkında konuşmak. Biz gerçekten sadece bahsediyoruz sağduyu ile bu kadar akıl, değil formüller veya delillerle, ya da böyle bir şey. Yani merak etmeyin, biz olmayacak Büyük bir matematik dersinde dönüşüyor. 

Yani biz karmaşıklık umurumda dedi o soruyu nasıl sorar çünkü Bizim algoritmaları büyük yapmalıyım ve Büyük veri kümeleri onlara atılan. Peki, bir veri kümesi nedir? Bunu derken ne demek istedi? En yapar ne demektir bağlamda duygusu, dürüst olmak gerekirse. Biz bir algoritma varsa Süreçler Strings-- muhtemelen konum dize boyutu bahsediyoruz. Bu veriler bu set-- boyutu, sayısı dize oluşturan karakterlerin. Biz hakkında konuşuyor dosyaları işleyen algoritması, Biz nasıl bahsediyoruz olabilir Birçok kilobayt bu dosyayı içermektedir. Ve bu veri seti var. Biz bir algoritma hakkında konuşuyor Bu, daha genel diziler kolları Böyle sıralama algoritmaları olarak veya algoritmaları arıyor, biz muhtemelen sayı bahsediyoruz bir dizi ihtiva elemanları. 

Şimdi, bir ölçebilirsiniz algorithm-- özellikle Diyorum zaman biz Ben, bir algoritma ölçmek Biz nasıl ölçebilirsiniz demek Birçok kaynak bu kadar sürer. Bu kaynaklar olsun, kaç RAM-- bayt veya RAM megabayt Kullandığı. Ya da ne kadar zaman çalıştırmak için alır. Ve biz bu çağırabilirsiniz n f, keyfi, ölçmek. Burada, n, sayısıdır veri kümesindeki elemanları. Ve n f kaç birşeyler olduğunu. Kaç kaynakların birimleri yapar bu verilerin işlenmesi için gereklidir. 

Şimdi, biz aslında umurumda değil Tam n f ne olduğu hakkında. Aslında, çok nadiren will-- Kesinlikle asla bu class-- I Herhangi gerçekten derin dalmak f n ne analizi. Biz sadece ne f hakkında konuşmak için gidiyoruz n yaklaşık ya da ne o eğilimi olduğunu. Ve bir algoritma eğilimidir en yüksek sipariş dönemi tarafından dikte. Ve biz ne görebiliyorum ben alarak bu demek Bir daha somut bir örneği inceleyelim. 

Yani biz diyelim Üç farklı algoritmalar. Ilki n alır Kaynakların küp, bazı birimler n büyüklüğünde bir veri kümesi işlem. Biz götüren ikinci bir algoritma var kuşbaşı artı n karesi kaynaklar n n büyüklüğünde bir veri kümesi işlem. Ve biz üçüncü var Bu açmayız çalışan algoritma kadar sürer n kuşbaşı eksi 8n karesi Kaynakların artı 20 n ünite bir algoritma işlemek n büyüklüğünde veri kümesi ile. 

Şimdi yine, biz gerçekten gitmiyor ayrıntı bu seviyede içine alır. Ben sadece bu kadar var gerçekten değilim Burada bir noktanın bir örnek olarak Ben olmak için gidiyorum Bir saniye içinde yapma hangi biz sadece gerçekten umurumda olduğunu şeylerin eğilimi hakkında veri setleri büyük olsun. Veri seti küçük Yani, orada aslında oldukça büyük bir fark Bu algoritmalar. Orada üçüncü algoritma 13 kat daha uzun sürer Kaynak 13 katıdır İlki göre çalıştırın. 

Bizim veri seti büyüklüğü 10 ise, hangi daha büyük, ama mutlaka büyük değil Biz var olduğunu görebiliyorum aslında bir fark biraz. Üçüncü algoritma daha verimli hale gelir. Aslında yaklaşık% 40 var - veya% 60 daha etkili. Bu% 40 zamanın miktarı alır. O alabilir run-- edebilirsiniz Kaynak 400 tane büyüklüğü 10 bir veri kümesi işlem. İlk Oysa algoritma, aksine, Kaynakların 1000 birimleri alır büyüklüğü 10 bir veri kümesi işlem. Ama ne olur bak Bizim sayılar daha da büyük olsun. 

Şimdi fark Bu algoritmalar arasındaki biraz daha az belirgin hale başlar. Olduğunu ve aslında düşük dereceli terms-- doğrusu Alt exponents-- ile terimler ilgisiz olmaya başlar. Bir veri kümesi boyutu ise 1000 ve birinci algoritma milyar adımda çalışır. Ve ikinci algoritma çalışır Bir milyar ve bir milyon adımlar. Ve üçüncü algoritma çalışır Bir milyar adımlar sadece utangaç içinde. Oldukça fazla bir milyar adımlar var. Bu alt-mertebeden terimler başlar Gerçekten önemsiz olmak. Ve sadece gerçekten eve çekiç point-- veri giriş boyutu a ise million-- tüm bu üç hemen hemen tek quintillion-- eğer almak benim matematik correct-- adım Bir veri giriş işlemek için boyut, bir milyon. Bu adımların bir sürü. Ve gerçeği onlardan biri olabilir Birkaç 100.000 ya da bir çift almak 100 milyon daha az zaman Biz bir sayı bahsediyoruz o tür alakasız big--. Hepsi almak eğilimindedir Yaklaşık n kuşbaşı, ve bu yüzden biz aslında bakın istiyorsunuz bu algoritmaların tüm n sırasına olarak kuşbaşı veya n kuşbaşı büyük-O. 

İşte daha bazılarının bir listesi Ortak hesaplama karmaşıklığı sınıfları Biz karşılaşacağınız o algoritmalar, genellikle,. Ayrıca spesifik olarak CS50 bölgesindeki. Bunlar sipariş edilir genellikle üst kısmında hızlı, altta genellikle yavaş etmek. Yani zaman sabiti algoritmaları eğilimindedir ne olursa olsun, en hızlı olmak için büyüklüğünün Veri girişi geçmek. Onlar her zaman bir işlem almak veya başa kaynakların bir birim. Bu 2 olabilir, bu olabilir 3 olmak, bu 4 olabilir. Ama sürekli bir numara. Bu değişmez. 

Logaritmik zaman algoritmaları biraz daha iyidir. Ve gerçekten iyi bir örnek logaritmik zaman algoritması mutlaka artık görülür ettik Telefon defterinin bölüyor telefon rehberinde Mike Smith'i bulmak için. Biz yarım sorunu kesti. N büyüdükçe böylece daha büyük ve larger-- Aslında, her zaman çift n, sadece bir adım daha sürer. Bu çok daha iyi yani daha, diyelim ki, lineer zaman. Eğer n çift ise Hangisi olduğunu adımlarla çift sayısını alır. Eğer n üçlü varsa, onu alır adımların sayısını üç katına. Birimin başına bir adım. 

Sonra işler biraz more-- olsun az harika oradan. Bazen, lineer ritmik zaman var Günlük doğrusal zaman denir ya sadece n log n. Ve biz bir örnek olacak bir algoritma bu hala iyidir n günlük n içinde çalışır daha karesel seferinde-- n karesi. Veya polinom zaman, n, ikidir ikiden daha büyük bir sayı. Veya üstel zamanı, burada Hatta worse-- Cı n etmektir. Bu yüzden bazı sabit sayı yükseldi giriş büyüklüğü gücü. Yani eğer 1,000-- varsa Veri giriş boyutu 1.000 taşımaktadır o 1000 iktidara C alacaktı. Bu polinom zaman çok daha kötü. 

Faktöriyel zaman daha da kötü. Ve aslında, gerçekten orada yapmak Sonsuz zaman algoritmalar var, olan, sözde, aptal sort-- iş rastgele bir dizi shuffle için ve sonra görmek için kontrol ister o tür var. Ve bu rastgele değilse Yine dizi shuffle ve olarak sıralanmış olup olmadığını kontrol edin. Ve muhtemelen imagine-- edebilirsiniz Eğer bir durum hayal edebiliyorum nerede kötü durumda, bu irade Aslında dizi ile başlar asla. Bu algoritma sonsuza çalışır. Ve böylece bir olurdu Sonsuz zaman algoritması. Umarım yazmaya olmayacak Herhangi bir faktöryel ya da sonsuz bir zaman CS50 algoritmalar. 

Yani, alalım biraz daha Bazı basit beton görünüm hesaplama karmaşıklığı sınıfları. Bu yüzden bir example-- var ya da iki örnek burada-- sabit zaman algoritmaları, hangi zaman alır kötü durumda bir tek çalışma. İlk example-- Yani Biz bir işlevi var Sizin için 4 adlandırılan hangi büyüklüğü 1000 bir dizi alır. Ama sonra anlaşılan Aslında görünmüyor bu-- gerçekten ne umursamıyor de , bunun içinde o dizinin. Her zaman sadece dört döndürür. Yani, bu algoritma, buna rağmen 1000 elemanları etmez alır Onlarla her şeyi yaparım. Sadece dört döndürür. Her zaman tek bir adımdır. 

Aslında, 2 nums-- katan biz Eee-- önce gördüm Sadece iki tamsayı işler. Tek bir adım değil. Aslında bir kaç adım var. Sen olsun, sen b olsun, bunları eklemek Birlikte ve çıkış sonuçlar. Yani 84 adımları var. Ancak bu her zaman sabittir ne olursa olsun, bir veya b. Bir almak zorunda, b, olsun, eklemek Birlikte onları çıkış sonucu. Yani sabit bir zaman algoritma var. 

İşte bir örnek Doğrusal zaman algorithm-- bu alan gets-- bir algoritma Bir ilave aşama, muhtemelen, senin girişi 1 ile büyüdükçe. Yani, biz arıyoruz diyelim Bir dizinin sayısı 5 iç. Bir durum nerede olabilir Eğer oldukça erken bulabilirsiniz. Ama aynı zamanda olabilir Bir durum nerede dizinin son elemanı olabilir. Büyüklüğü 5 bir dizi, eğer içinde Biz numara 5 arıyoruz. Bu 5 adım alacaktı. Ve aslında, var olduğunu hayal Bu dizide değil 5 her yerde. Biz hala aslında bakmak zorunda Dizinin her elemanı belirlemek amacıyla olsun ya da 5 vardır. 

Böylece en kötü-durumunda, eleman dizideki son olduğunu ya da hiç yok. Biz hala bakmak zorunda n bütün elemanları. Ve böylece bu algoritma Doğrusal zamanla çalışır. Sen tarafından teyit edebilirsiniz diyerek biraz extrapolating, Biz 6-element dizi olsaydı ve Biz numara 5 için aradılar o 6 adımları sürebilir. Biz 7 elemanlı dizi varsa ve Biz numara 5 arıyoruz. Bu 7 adımlar olabilir. Biz bir daha eleman eklemek gibi bizim Dizi, bir daha adım attı. Bu doğrusal bir algoritma var kötü durumda. 

Çift sizin için hızlı soru. Ne runtime-- neler var en kötü durum zamanı Bu kod belirli snippet'in? Yani çalışan Burada 4 döngü var j 0, m'ye kadar tüm yol eşittir dan. Ve ben burada görüyorum olduğunu döngünün gövdesi sabit zamanda çalışır. Yani terminoloji bu kullanarak biz zaten ne hakkında konuştuk ettik En kötü durumda olurdu Bu algoritmanın çalışma zamanı? Bir saniye sürer. Döngüsünün iç kısmında sabit zamanda çalışır. Ve dış kısmı loop m kez çalıştırmak için gidiyor. Yani en kötü durum çalışma zamanı burada ne var? Eğer m büyük-O tahmin mi? Sen haklı olurdunuz. 

Nasıl başka bir dersin? Biz var bu kez Bir döngü içinde döngü. Biz bir dış döngü var Bu sıfırdan p çalışır. Ve biz çalışan bir iç döngü var sıfırdan p ve bunun içinde Ben devlet vücut o loop sabit zamanda çalışır. Yani en kötü durum zamanı ne Bu kod belirli snippet'in? Peki, yine, biz bir var p kez çalışır dış döngü. Ve her defasında bir yineleme Bu döngü, daha çok. Biz bir iç döngü var bu da p kez çalışır. Bunun içinde Ve sonra, orada Orada sürekli seferinde-- küçük pasajı. 

Biz bir dış döngü varsa Böylece hangi bir iç p kez çalışır Bir iç döngü bu ne times-- p çalışır en kötü durum zamanı Bu kod parçacığını? Eğer p büyük-O karesi tahmin mı? 

Ben Doug Lloyd değilim. Bu CS50 olduğunu.