[Powered by Google Translate] Bạn đã từng nghe người ta nói về một thuật toán nhanh hoặc hiệu quả
để thực hiện nhiệm vụ cụ thể của bạn,
nhưng chính xác những gì nó có nghĩa là một thuật toán để được nhanh chóng hoặc hiệu quả?
Vâng, nó không nói về đo lường trong thời gian thực,
giống như giây hoặc vài phút.
Điều này là do phần cứng máy tính
và phần mềm khác nhau đáng kể.
Chương trình của tôi có thể chạy chậm hơn so với của bạn,
bởi vì tôi đang chạy nó trên một máy tính cũ,
hoặc bởi vì tôi xảy ra để được chơi một trò chơi video trực tuyến
cùng một lúc, được hogging tất cả các bộ nhớ của tôi,
hoặc tôi có thể chạy chương trình của tôi thông qua phần mềm khác nhau
mà giao tiếp với máy khác nhau ở mức độ thấp.
Nó giống như so sánh táo và cam.
Chỉ vì máy tính của tôi chậm hơn mất nhiều thời gian
hơn của bạn để cung cấp cho một câu trả lời
không có nghĩa là bạn có thuật toán hiệu quả hơn.
>> Vì vậy, kể từ khi chúng tôi không thể so sánh trực tiếp các runtimes của các chương trình
trong vài giây hoặc vài phút,
làm thế nào để chúng ta so sánh 2 thuật toán khác nhau
bất kể phần cứng hoặc phần mềm môi trường?
Để tạo ra một cách đồng đều hơn của đo lường hiệu quả thuật toán,
các nhà khoa học máy tính và toán học đã phát minh ra
khái niệm để đo sự phức tạp tiệm cận của một chương trình
và một ký hiệu được gọi là "Big Ohnotation '
để mô tả điều này.
Định nghĩa chính thức là một hàm f (x)
chạy trên thứ tự của g (x)
nếu có tồn tại một số giá trị (x), x ₀ và
một số không đổi, C, mà
f (x) nhỏ hơn hoặc bằng
rằng thời gian liên tục g (x)
cho tất cả các x lớn hơn x ₀.
>> Tuy nhiên, không được sợ hãi bởi các định nghĩa chính thức.
Điều này có thực sự có ý nghĩa trong ít về lý thuyết?
Vâng, đó là cơ bản một cách phân tích
nhanh như thế nào thời gian chạy của một chương trình phát triển tiệm.
Đó là, như kích thước của đầu vào của bạn tăng theo hướng vô cùng,
nói rằng, bạn đang phân loại một loạt các kích cỡ 1000 so với một mảng có kích thước là 10.
Thời gian chạy của chương trình của bạn phát triển như thế nào?
Ví dụ, hãy tưởng tượng đếm số ký tự
trong một chuỗi cách đơn giản nhất
bằng cách đi bộ qua toàn bộ chuỗi
thư-by-thư và cộng thêm 1 vào một truy cập cho mỗi ký tự.
Thuật toán này được cho là chạy trong thời gian tuyến tính
đối với số ký tự,
'N' trong chuỗi.
Trong ngắn hạn, nó chạy trong O (n).
Tại sao điều này?
Vâng, bằng cách sử dụng phương pháp này, thời gian cần thiết
đi qua toàn bộ chuỗi
là tỷ lệ thuận với số lượng ký tự.
Đếm số ký tự trong một chuỗi 20 ký tự
là sẽ mất gấp đôi thời gian như nó cần
để đếm số ký tự trong một chuỗi 10 ký tự,
bởi vì bạn phải nhìn vào tất cả các nhân vật
và mỗi nhân vật có cùng một lượng thời gian để xem xét.
Khi bạn tăng số ký tự,
thời gian chạy sẽ tăng tuyến tính với chiều dài đầu vào.
>> Bây giờ, hãy tưởng tượng nếu bạn quyết định rằng thời gian tuyến tính,
O (n), chỉ là không đủ nhanh cho bạn?
Có lẽ bạn đang lưu trữ chuỗi rất lớn,
và bạn không thể đủ khả năng thêm thời gian nó sẽ mất
đi qua tất cả các ký tự của họ đếm một-by-một.
Vì vậy, bạn quyết định thử một cái gì đó khác nhau.
Bạn nếu những gì sẽ xảy ra cho đã lưu trữ số lượng ký tự
trong chuỗi, nói, trong một biến gọi là 'len,
sớm trong chương trình,
thậm chí trước khi bạn lưu trữ các ký tự đầu tiên trong chuỗi của bạn?
Sau đó, tất cả những gì bạn phải làm bây giờ để tìm ra chiều dài chuỗi,
là kiểm tra những gì giá trị của biến.
Bạn sẽ không phải nhìn vào chuỗi chính nó ở tất cả,
và truy cập các giá trị của một biến như len được coi là
một thời gian hoạt động liên tục tiệm,
O (1).
Tại sao điều này? Vâng, nhớ tiệm cận phức tạp có nghĩa là gì.
Làm thế nào để thay đổi thời gian chạy như kích thước
của bạn đầu vào phát triển?
>> Nói rằng bạn đã cố gắng để có được số ký tự trong một chuỗi lớn hơn.
Vâng, nó sẽ không có vấn đề lớn như thế nào bạn thực hiện các chuỗi,
thậm chí một triệu ký tự dài,
tất cả các bạn sẽ phải làm gì để tìm độ dài của chuỗi với cách tiếp cận này,
là để đọc ra các giá trị của len biến,
mà bạn đã thực hiện.
Chiều dài đầu vào, có nghĩa là, chiều dài của chuỗi bạn đang cố gắng để tìm thấy,
không ảnh hưởng đến ở tất cả các chương trình của bạn chạy nhanh như thế nào.
Điều này một phần của chương trình của bạn sẽ chạy như nhau nhanh trên một chuỗi ký tự
và một chuỗi hàng nghìn ký tự,
và đó là lý do tại sao chương trình này sẽ được gọi là chạy trong thời gian liên tục
đối với kích thước đầu vào.
>> Tất nhiên, có một nhược điểm.
Bạn dành thêm không gian bộ nhớ trên máy tính của bạn
lưu trữ các biến
và thêm thời gian nó sẽ đưa bạn
để làm các việc lưu trữ thực tế của biến,
nhưng điểm vẫn đứng,
tìm ra chuỗi của bạn là bao lâu
không phụ thuộc vào chiều dài của chuỗi ở tất cả.
Vì vậy, nó chạy trong O (1) thời gian liên tục.
Điều này chắc chắn không phải có nghĩa là
rằng mã của bạn chạy trong 1 bước,
nhưng không có vấn đề bao nhiêu bước nó là,
nếu nó không thay đổi với kích thước của các yếu tố đầu vào,
nó vẫn còn tiệm liên tục mà chúng tôi đại diện là O (1).
>> Như bạn có thể đoán,
có rất nhiều khác nhau runtimes O lớn để đo lường các thuật toán với.
O (n) ² thuật toán là tiệm chậm hơn so với các thuật toán O (n).
Đó là, là số phần tử (n) phát triển,
cuối cùng O (n) ² thuật toán sẽ mất thời gian nhiều hơn
hơn so với các thuật toán O (n) để chạy.
Điều này không có nghĩa là thuật toán O (n) luôn luôn chạy nhanh hơn
hơn so với O (n) ² thuật toán, ngay cả trong cùng một môi trường,
trên cùng một phần cứng.
Có lẽ đối với kích thước đầu vào nhỏ,
O (n) ² thuật toán thực sự có thể làm việc nhanh hơn,
nhưng, cuối cùng, như kích thước đầu vào tăng
hướng tới vô cùng, O (n) ² thời gian chạy của thuật toán
cuối cùng sẽ làm lu mờ thời gian chạy của thuật toán O (n).
Cũng giống như bất kỳ chức năng toán học bậc hai
cuối cùng sẽ vượt qua bất kỳ chức năng tuyến tính,
không có vấn đề bao nhiêu đầu bắt đầu chức năng tuyến tính bắt đầu.
Nếu bạn đang làm việc với số lượng lớn dữ liệu,
thuật toán chạy trong O (n) ² thời gian thực sự có thể kết thúc làm chậm chương trình của bạn,
nhưng đối với kích thước đầu vào nhỏ,
có thể bạn sẽ không nhận thấy.
>> Một phức tạp tiệm cận là,
lôgarít thời gian, O (log n).
Một ví dụ của một thuật toán chạy một cách nhanh chóng
là thuật toán tìm kiếm nhị phân cổ điển,
cho việc tìm kiếm một phần tử trong một danh sách đã được sắp xếp của các nguyên tố.
>> Nếu bạn không biết những gì tìm kiếm nhị phân,
Tôi sẽ giải thích cho bạn thực sự nhanh chóng.
Hãy nói rằng bạn đang tìm kiếm số 3
trong mảng các số nguyên.
Nó nhìn vào các phần tử giữa của mảng
và hỏi, "các yếu tố tôi muốn lớn hơn, bằng, hoặc ít hơn này?"
Nếu đó là bằng nhau, sau đó tuyệt vời. Bạn tìm thấy các yếu tố, và bạn đang làm.
Nếu nó lớn hơn, sau đó bạn biết các phần tử
có phải là ở phía bên phải của mảng,
và bạn chỉ có thể nhìn vào đó trong tương lai,
và nếu nó nhỏ hơn, sau đó bạn biết nó có phải là ở phía bên trái.
Sau đó, quá trình này được lặp đi lặp lại với các mảng nhỏ hơn kích thước
cho đến khi các yếu tố chính xác được tìm thấy.
>> Thuật toán này mạnh mẽ cắt giảm kích thước mảng một nửa với mỗi hoạt động.
Vì vậy, để tìm một phần tử trong một mảng được sắp xếp có kích thước 8,
nhiều nhất (đăng nhập ₂ 8)
hoặc 3 của các hoạt động này,
sẽ được yêu cầu kiểm tra các yếu tố trung lưu, sau đó cắt các mảng trong một nửa,
trong khi một mảng có kích thước 16 mất (đăng nhập ₂ 16),
4 hoạt động.
Đó là chỉ có 1 hoạt động cho một mảng tăng gấp đôi kích thước.
Tăng gấp đôi kích thước của mảng
tăng thời gian chạy chỉ có 1 đoạn mã này.
Một lần nữa, kiểm tra các yếu tố giữa của danh sách, sau đó chia tách.
Vì vậy, nó hoạt động trong thời gian lôgarít,
O (log n).
Nhưng chờ đợi, bạn nói,
không phụ thuộc vào nơi trong danh sách các yếu tố bạn đang tìm kiếm?
Điều gì sẽ xảy ra nếu các yếu tố đầu tiên bạn nhìn vào sẽ xảy ra là một trong những quyền?
Sau đó, nó chỉ mất 1 hoạt động,
không có vấn đề lớn như thế nào trong danh sách là.
>> Vâng, đó là lý do tại sao các nhà khoa học máy tính có nhiều điều kiện hơn
phức tạp tiệm cận, phản ánh trường hợp tốt nhất
và trường hợp xấu nhất biểu diễn của một thuật toán.
Đúng hơn, trên và dưới giới hạn
thời gian chạy.
Trong trường hợp tốt nhất cho tìm kiếm nhị phân, phần tử của chúng tôi là
phải có ở giữa,
và bạn nhận được nó trong thời gian liên tục,
không có vấn đề lớn như thế nào phần còn lại của mảng.
Các biểu tượng được sử dụng cho điều này là Ω.
Vì vậy, thuật toán này được cho là để chạy trong Ω (1).
Trong trường hợp tốt nhất, nó tìm thấy các phần tử một cách nhanh chóng,
không có vấn đề mảng lớn như thế nào,
nhưng trong trường hợp xấu nhất,
nó có để thực hiện (log n) kiểm tra phân chia
của mảng để tìm các phần tử bên phải.
Giới hạn trường hợp xấu nhất trên được gọi lớn "O" mà bạn đã biết.
Vì vậy, nó là O (log n), nhưng Ω (1).
>> Một tìm kiếm tuyến tính, ngược lại,
trong đó bạn đi bộ qua tất cả các phần tử của mảng
để tìm thấy một trong những bạn muốn,
là tốt nhất Ω (1).
Một lần nữa, các yếu tố đầu tiên mà bạn muốn.
Vì vậy, nó không quan trọng mảng lớn như thế nào.
Trong trường hợp xấu nhất, đó là yếu tố cuối cùng trong mảng.
Vì vậy, bạn phải đi bộ qua tất cả các yếu tố n trong mảng để tìm thấy nó,
giống như nếu bạn đang tìm kiếm 3 a.
Vì vậy, nó chạy trong thời gian O (n)
bởi vì nó tỷ lệ thuận với số lượng phần tử trong mảng.
>> Một biểu tượng được sử dụng là Θ.
Điều này có thể được sử dụng để mô tả các thuật toán của các trường hợp tốt nhất và tồi tệ nhất
đều giống nhau.
Đây là trường hợp trong các thuật toán chuỗi dài, chúng ta đã nói trước đó.
Đó là, nếu chúng ta lưu trữ nó trong một biến trước khi
chúng tôi lưu trữ các chuỗi và truy cập nó sau trong thời gian liên tục.
Không có vấn đề gì số
chúng tôi đang lưu trữ trong biến đó, chúng tôi sẽ phải nhìn vào nó.
Trường hợp tốt nhất, chúng ta nhìn vào nó
và tìm thấy chiều dài của chuỗi.
Vì vậy, Ω (1) hoặc tốt nhất trường hợp thời gian liên tục.
Trường hợp xấu nhất là,
chúng ta nhìn vào nó và tìm ra chiều dài của chuỗi.
Vì vậy, O (1) thời gian liên tục trong trường hợp xấu nhất.
Vì vậy, kể từ khi trường hợp tốt nhất và trường hợp xấu nhất là như nhau,
này có thể được cho biết để chạy trong thời gian (1) Θ.
>> Tóm lại, chúng ta có những cách tốt để lý do về mã hiệu quả
mà không biết bất cứ điều gì về thời gian thực tế họ để chạy,
bị ảnh hưởng bởi rất nhiều yếu tố bên ngoài,
bao gồm cả phần cứng khác nhau, phần mềm,
hoặc các chi tiết cụ thể của mã của bạn.
Ngoài ra, nó cho phép chúng ta để lý do về những gì sẽ xảy ra
khi kích thước của sự gia tăng đầu vào.
>> Nếu bạn đang chạy trong thuật toán O ² (n),
hoặc tệ hơn, một O (2 ⁿ) thuật toán,
một trong những loại phát triển nhanh nhất,
bạn thực sự sẽ bắt đầu nhận thấy sự suy giảm
khi bạn bắt đầu làm việc với số lượng lớn dữ liệu.
>> Đó là tiệm cận phức tạp. Cảm ơn.