Tất cả các quyền, do đó, tính toán phức tạp. Chỉ cần một chút của một cảnh báo trước khi chúng ta đi sâu vào quá far-- điều này có lẽ sẽ là một trong số những điều nhất môn toán nặng chúng ta nói về trong CS50. Hy vọng rằng nó sẽ không quá áp đảo và chúng tôi sẽ cố gắng và hướng dẫn bạn thông qua quá trình này, nhưng chỉ là một chút của một cảnh báo công bằng. Có một chút của toán học liên quan ở đây. Được rồi, vì vậy để làm cho sử dụng các tài nguyên tính toán của chúng tôi trong world-- thực sự nó thực sự quan trọng để hiểu các thuật toán và làm thế nào họ xử lý dữ liệu. Nếu chúng ta có một thực sự thuật toán hiệu quả, chúng tôi có thể giảm thiểu số lượng tài nguyên chúng tôi có sẵn để đối phó với nó. Nếu chúng ta có một thuật toán mà là sẽ mất rất nhiều công việc để xử lý một thực sự tập dữ liệu lớn, nó sẽ đòi hỏi nhiều hơn và nhiều tài nguyên, mà là tiền bạc, RAM, tất cả các loại công cụ. 

Vì vậy, để có thể phân tích một thuật toán sử dụng bộ công cụ này, về cơ bản, yêu cầu các question-- làm thế nào quy mô thuật toán này như chúng ta ném càng nhiều dữ liệu vào nó? Trong CS50, số lượng dữ liệu chúng tôi làm việc với là khá nhỏ. Nói chung, các chương trình của chúng tôi sẽ để chạy trong một giây hoặc less-- có lẽ ít hơn rất nhiều đặc biệt vào đầu. 

Nhưng hãy nghĩ về một công ty giao dịch với hàng trăm triệu khách hàng. Và họ cần xử lý rằng dữ liệu khách hàng. Khi số lượng khách hàng của họ có được lớn hơn và lớn hơn, nó sẽ yêu cầu hơn và nhiều tài nguyên. Làm thế nào nhiều hơn các nguồn lực? Vâng, điều đó phụ thuộc vào cách chúng tôi phân tích các thuật toán, sử dụng các công cụ trong hộp công cụ này. Khi chúng ta nói về sự phức tạp của một algorithm-- mà đôi khi bạn sẽ nghe nó gọi là thời gian phức tạp hoặc không gian phức tạp nhưng chúng tôi chỉ cần đi để gọi complexity-- nói chung chúng ta đang nói về các trường hợp xấu nhất. Với đống tuyệt đối tồi tệ nhất của dữ liệu mà chúng tôi có thể được ném vào nó, làm thế nào là thuật toán này sẽ xử lý hoặc xử lý dữ liệu đó? Chúng tôi thường gọi trường hợp xấu nhất thời gian chạy của một thuật toán O lớn. Vì vậy, một thuật toán có thể được nói đến chạy trong O của n hoặc O của n bình phương. Và nhiều hơn nữa về những gì những người có nghĩa là trong một giây. 

Đôi khi, mặc dù, chúng tôi chăm sóc về các trường hợp tốt nhất. Nếu dữ liệu là tất cả mọi thứ chúng tôi muốn nó được và nó đã được hoàn toàn hoàn hảo và chúng tôi đã gửi hoàn hảo này thiết lập các dữ liệu thông qua các thuật toán của chúng tôi. Làm thế nào nó sẽ xử lý trong tình huống đó? Chúng ta đôi khi chỉ đến đó như big-Omega, vì vậy trong tương phản với big-O, chúng tôi có lớn Omega. Big-Omega cho các trường hợp tốt nhất. Big-O cho các trường hợp xấu nhất. Nói chung, khi chúng ta nói về sự phức tạp của một thuật toán, chúng ta đang nói về trường hợp xấu nhất kịch bản. Vì vậy, giữ cho rằng trong tâm trí. 

Và trong lớp học này, chúng ta thường đi để lại những phân tích nghiêm ngặt sang một bên. Có khoa học và các lĩnh vực dành cho loại công cụ này. Khi chúng ta nói về lý luận thông qua các thuật toán, mà chúng tôi sẽ làm piece-by-piece cho nhiều các thuật toán chúng ta nói về trong lớp. Chúng tôi đang thực sự chỉ nói về lý luận thông qua nó với ý nghĩa thông thường, không có công thức, hoặc giấy tờ chứng minh, hoặc bất cứ điều gì như thế. Vì vậy, đừng lo lắng, chúng tôi sẽ không được biến thành một lớp toán học lớn. 

Vì vậy, tôi đã nói, chúng tôi quan tâm về sự phức tạp bởi vì nó đưa ra câu hỏi, làm thế nào làm các thuật toán của chúng tôi xử lý lớn hơn và các tập dữ liệu lớn được ném vào chúng. Vâng, một tập hợp dữ liệu là gì? Tôi đã có ý nghĩa gì khi tôi nói vậy? Nó có nghĩa là bất cứ điều gì làm cho hầu hết ý nghĩa trong bối cảnh, phải trung thực. Nếu chúng ta có một thuật toán, Processes Strings-- chúng tôi có thể nói về kích thước của chuỗi. Đó là các dữ liệu set-- kích thước, số lượng các ký tự tạo nên các chuỗi. Nếu chúng ta đang nói về một thuật toán xử lý các tập tin, chúng ta có thể nói về cách nhiều kilobytes gồm tập tin đó. Và đó là tập hợp dữ liệu. Nếu chúng ta đang nói về một thuật toán xử lý mảng thường hơn, chẳng hạn như thuật toán phân loại hoặc tìm kiếm các thuật toán, có lẽ chúng ta đang nói về số lượng các yếu tố đó bao gồm một mảng. 

Bây giờ, chúng ta có thể đo lường một algorithm-- nói riêng, khi tôi nói rằng chúng tôi có thể đo một thuật toán, tôi có nghĩa là chúng ta có thể đo lường như thế nào nhiều nguồn lực nó chiếm. Cho dù những nguồn lực đang có, bao nhiêu byte của RAM-- hoặc MB RAM nó sử dụng. Hoặc có bao nhiêu thời gian để chạy. Và chúng ta có thể gọi đây đo lường, tùy tiện, f của n. Trong đó n là số các phần tử trong tập hợp dữ liệu. Và f của n là bao nhiêu somethings. Có bao nhiêu đơn vị tài nguyên không nó yêu cầu để xử lý dữ liệu đó. 

Bây giờ, chúng tôi thực sự không quan tâm về những gì f của n là chính xác. Trong thực tế, chúng tôi rất hiếm khi will-- chắc chắn sẽ không bao giờ trong tôi class-- này nhảy vào bất kỳ thực sự sâu sắc phân tích của f của n là gì. Chúng tôi chỉ cần đi để nói về những gì e n là xấp xỉ hoặc những gì nó có xu hướng. Và xu hướng của một thuật toán là quyết định bởi hạn mức độ cao nhất của nó. Và chúng ta có thể thấy những gì tôi ý nghĩa bởi đó bằng cách tham gia một nhìn vào một ví dụ cụ thể hơn. 

Vì vậy, chúng ta hãy nói rằng chúng tôi có ba thuật toán khác nhau. Việc đầu tiên trong số đó có n cubed, một số đơn vị tài nguyên để xử lý một tập hợp dữ liệu có kích thước n. Chúng tôi có một thuật toán thứ hai mà phải mất n cubed cộng với nguồn n bình để xử lý một tập hợp dữ liệu có kích thước n. Và chúng tôi có một phần ba thuật toán chạy in-- đó chiếm n trừ cubed 8N phương cộng với 20 n đơn vị tài nguyên để xử lý một thuật toán với dữ liệu thiết lập kích thước n. 

Bây giờ một lần nữa, chúng ta thật sự không hẹn để có được vào mức độ chi tiết này. Tôi thực sự chỉ có những lên ở đây như là một minh họa của một điểm rằng tôi sẽ được làm trong một giây, là chúng ta chỉ thực sự quan tâm về xu hướng của sự vật như các bộ dữ liệu có được lớn hơn. Vì vậy, nếu các tập dữ liệu là nhỏ, có thực sự là một sự khác biệt khá lớn trong các thuật toán. Các thuật toán thứ ba có mất lâu hơn 13 lần, 13 lần số lượng tài nguyên để chạy tương đối với một trong những đầu tiên. 

Nếu dữ liệu của chúng tôi là kích thước 10, là lớn hơn, nhưng không nhất thiết là rất lớn, chúng ta có thể thấy rằng có thực sự là một chút của một sự khác biệt. Các thuật toán thứ ba trở nên hiệu quả hơn. Đó là về thực 40% - hoặc 60% hiệu quả hơn. Phải mất 40% số lượng thời gian. Nó có thể run-- nó có thể mất 400 đơn vị tài nguyên để xử lý một tập hợp dữ liệu có kích thước 10. Trong khi đó, người đầu tiên thuật toán, ngược lại, có 1.000 đơn vị tài nguyên để xử lý một tập hợp dữ liệu có kích thước 10. Nhưng hãy nhìn những gì xảy ra khi số của chúng tôi nhận được thậm chí lớn hơn. 

Bây giờ, sự khác biệt giữa các thuật toán bắt đầu trở thành một chút ít rõ ràng hơn. Và thực tế là có thấp hơn để terms-- hay đúng hơn, các điều khoản với exponents-- thấp bắt đầu trở nên không thích hợp. Nếu một tập hợp dữ liệu có kích thước 1000 và các thuật toán đầu tiên chạy trong một tỷ bước. Và các thuật toán thứ hai chạy trong một tỷ đồng và một triệu bước. Và các thuật toán thứ ba chạy trong chỉ nhút nhát của một tỷ bước. Đó là khá nhiều một tỷ bước. Những điều khoản dưới để bắt đầu để trở nên thực sự không thích hợp. Và chỉ để thực sự búa nhà point-- nếu các dữ liệu đầu vào là có kích thước một million-- cả ba khá nhiều mất một quintillion-- nếu toán học của tôi là bước correct-- để xử lý dữ liệu đầu vào kích thước của một triệu. Đó là rất nhiều bước. Và thực tế là một trong số họ có thể mất một vài 100,000, hoặc một vài 100 triệu thậm chí ít khi chúng ta đang nói về một số rằng big-- đó là loại không thích hợp. Họ đều có xu hướng mất khoảng n cubed, và vì vậy chúng tôi sẽ thực sự tham khảo cho tất cả các thuật toán như là vào thứ tự của n cubed hoặc O lớn của n cubed. 

Dưới đây là một danh sách của một số chi tiết lớp phức tạp tính toán thông thường rằng chúng ta sẽ gặp phải trong các thuật toán, nói chung. Và cũng đặc biệt trong CS50. Chúng được đặt hàng từ nói chung là nhanh nhất ở đầu, để thường chậm nhất ở phía dưới. Vì vậy, các thuật toán thời gian liên tục có xu hướng là nhanh nhất, không phân biệt các kích thước của dữ liệu đầu vào bạn vượt qua trong. Họ luôn luôn có một hoạt động hoặc một đơn vị nguồn lực để đối phó với. Nó có thể là 2, nó có thể được 3, nó có thể là 4. Nhưng đó là một hằng số. Nó không thay đổi. 

Thuật toán thời gian logarit là tốt hơn một chút. Và một ví dụ thực sự tốt của một thuật toán thời gian logarit bạn đã chắc chắn nhìn thấy bây giờ là xé nát của cuốn sách điện thoại để tìm Mike Smith trong sổ điện thoại. Chúng tôi cắt các vấn đề trong một nửa. Và như vậy, n được lớn hơn và lớn hơn và larger-- trên thực tế, mỗi khi bạn tăng gấp đôi n, nó chỉ mất một bước nữa. Vì vậy, đó là tốt hơn rất nhiều hơn, nói, thời gian tuyến tính. Đó là nếu bạn tăng gấp đôi n, nó mất gấp đôi số lượng các bước. Nếu bạn tăng gấp ba n, phải mất tăng gấp ba lần số lượng các bước. Một bước trên một đơn vị. 

Sau đó, việc có được một chút more-- chút ít tuyệt vời từ đó. Bạn có thời gian tuyến tính nhịp điệu, đôi khi gọi là nhật ký thời gian tuyến tính, hoặc chỉ n log n. Và chúng tôi sẽ là một ví dụ của một thuật toán mà chạy trong n n log, mà vẫn còn tốt hơn hơn bậc hai time-- n bình phương. Hoặc thời gian đa thức, n hai bất kỳ số nào lớn hơn hai. Hoặc thời gian mũ, mà thậm chí còn worse-- C đến n. Vì vậy, một số số liên tục tăng lên sức mạnh của các kích thước của đầu vào. Vì vậy, nếu có 1,000-- nếu dữ liệu đầu vào là có kích thước 1.000, nó sẽ mất C với sức mạnh 1000. Nó tồi tệ hơn rất nhiều so với thời gian đa thức. 

Thời gian thừa thậm chí còn tồi tệ hơn. Và trên thực tế, có thực sự làm tồn tại thuật toán thời gian vô hạn, chẳng hạn như, cái gọi là ngu ngốc mà sort-- công việc là để shuffle ngẫu nhiên một mảng và sau đó kiểm tra xem cho dù nó được sắp xếp. Và nếu nó không phải, ngẫu nhiên xáo trộn các mảng lại và kiểm tra để xem liệu nó được sắp xếp. Và như bạn có thể có thể imagine-- bạn có thể tưởng tượng một tình huống nơi mà trong trường hợp xấu nhất, có ý chí không bao giờ thực sự bắt đầu với mảng. Thuật toán mà có thể chạy mãi. Và do đó sẽ là một vô hạn thuật toán thời gian. Hy vọng rằng bạn sẽ không được viết bất cứ lúc nào thừa hoặc vô hạn thuật toán trong CS50. 

Vì vậy, chúng ta hãy thêm một chút cái nhìn cụ thể tại một số đơn giản lớp học tính toán phức tạp. Vì vậy, chúng ta có một example-- hoặc hai ví dụ here-- các thuật toán thời gian liên tục, mà luôn luôn đi một hoạt động duy nhất trong trường hợp xấu nhất. Vì vậy, các example-- đầu tiên chúng tôi có một chức năng gọi là 4 cho bạn, mà mất một mảng có kích thước 1.000. Nhưng sau đó rõ ràng không thực sự nhìn tại it-- không thực sự quan tâm những gì bên trong của nó, của mảng đó. Lúc nào cũng chỉ trả về bốn. Vì vậy, thuật toán, mặc dù thực tế rằng nó mất 1.000 yếu tố không làm bất cứ điều gì với họ. Chỉ cần trả về bốn. Nó luôn luôn là một bước duy nhất. 

Trong thực tế, thêm 2 nums-- mà chúng tôi đã nhìn thấy trước như well-- chỉ xử lý hai số nguyên. Nó không phải là một bước duy nhất. Nó thực sự là một vài bước. Bạn nhận được một, bạn sẽ có được b, bạn thêm chúng với nhau, và bạn xuất kết quả. Vì vậy, nó là 84 bước. Nhưng nó luôn luôn không đổi, bất kể một hoặc b. Bạn có để có được một, có được b, thêm chúng lại với nhau, kết quả đầu ra. Vì vậy, đó là một thuật toán thời gian liên tục. 

Dưới đây là một ví dụ về một thời gian tuyến tính algorithm-- một thuật toán mà gets-- mà mất một bước bổ sung, có thể, như là đầu vào của bạn phát triển bởi 1. Vì vậy, chúng ta hãy nói rằng chúng tôi đang tìm kiếm số 5 bên trong một mảng. Bạn có thể có một tình huống mà bạn có thể tìm thấy nó khá sớm. Nhưng bạn cũng có thể có một tình huống mà nó có thể là yếu tố cuối cùng của mảng. Trong một mảng có kích thước 5, nếu chúng tôi đang tìm kiếm các số 5. Nó sẽ có 5 bước. Và trên thực tế, hãy tưởng tượng rằng có không phải 5 bất cứ nơi nào trong mảng này. Chúng tôi vẫn thực sự phải nhìn vào mỗi phần tử của mảng nhằm xác định hay không 5 là có. 

Vì vậy, trong trường hợp xấu nhất, đó là các nguyên tố là cuối cùng trong mảng hoặc không tồn tại. Chúng tôi vẫn phải nhìn vào tất cả các yếu tố n. Và do đó, thuật toán này chạy trong thời gian tuyến tính. Bạn có thể xác nhận rằng bằng ngoại suy một chút bằng cách nói, nếu chúng ta có một mảng 6 phần tử và chúng tôi đang tìm kiếm các số 5, nó có thể mất 6 bước. Nếu chúng ta có một mảng 7 phần tử và chúng tôi đang tìm kiếm các số 5. Nó có thể mất 7 bước. Khi chúng ta thêm một yếu tố nữa để chúng tôi mảng, phải mất thêm một bước nữa. Đó là một thuật toán tuyến tính trong trường hợp xấu nhất. 

Vài câu hỏi nhanh chóng cho bạn. Các runtime-- những gì là những gì trường hợp xấu nhất-runtime của đoạn này đặc biệt của mã? Vì vậy, tôi có một vòng lặp 4 ở đây mà chạy từ j bằng 0, tất cả các con đường lên đến m. Và những gì tôi nhìn thấy ở đây, là các thân của vòng lặp chạy trong thời gian liên tục. Vì vậy, bằng cách sử dụng các thuật ngữ chúng tôi đã nói chuyện gì about-- sẽ là trường hợp xấu nhất thời gian chạy của thuật toán này? Mất một giây. Phần bên trong của vòng lặp chạy trong thời gian liên tục. Và phần ngoài của vòng lặp sẽ chạy lần m. Vì vậy, thời gian chạy trường hợp xấu nhất ở đây là gì? Bạn có đoán big-O của m? Bạn muốn được bên phải. 

Làm thế nào về nhau? Hiện nay chúng tôi có một vòng lặp bên trong một vòng lặp. Chúng tôi có một vòng ngoài chạy từ số không đến p. Và chúng ta có một vòng lặp bên trong chạy từ số không đến p, và bên trong đó, Tôi tuyên bố rằng cơ thể vòng lặp chạy trong thời gian liên tục. Vì vậy, thời gian chạy trường hợp xấu nhất là gì của đoạn này đặc biệt của mã? Vâng, một lần nữa, chúng ta có một vòng ngoài mà chạy lần p. Và mỗi lần lặp time-- vòng lặp đó, thay. Chúng tôi có một vòng trong mà cũng chạy lần p. Và sau đó bên trong đó, có các hằng time-- ít đoạn đó. 

Vì vậy, nếu chúng ta có một vòng lặp bên ngoài mà chạy p lần bên trong đó là một vòng lặp bên đó chạy p times-- là gì trường hợp xấu nhất-runtime của đoạn mã này? Bạn có đoán O lớn của p bình phương? 

Tôi Doug Lloyd. Đây là CS50.