Câu hỏi Giải thích bằng tiếng Anh đơn giản về ký hiệu “Big O” là gì?


Tôi muốn càng ít định nghĩa chính thức càng tốt và toán học đơn giản.


4533
2018-01-28 11:10


gốc


Tóm tắt: Giới hạn trên của độ phức tạp của thuật toán. Xem thêm câu hỏi tương tự Big O, làm thế nào để bạn tính toán / ước lượng nó? cho một giải thích tốt. - Kosi2801
Các câu trả lời khác khá tốt, chỉ cần một chi tiết để hiểu nó: O (log n) hoặc các phương tiện tương tự, rằng nó phụ thuộc vào "chiều dài" hoặc "kích thước" của đầu vào, không phải trên chính giá trị đó. Điều này có thể khó hiểu nhưng rất quan trọng. Ví dụ, điều này xảy ra khi thuật toán của bạn chia tách mọi thứ thành hai trong mỗi lần lặp. - Harald Schilly
Có một bài giảng dành riêng cho sự phức tạp của các thuật toán trong Bài giảng 8 của khóa học "Giới thiệu về Khoa học Máy tính và Lập trình" của MIT youtube.com/watch?v=ewd7Lf2dr5Q Nó không phải là hoàn toàn đơn giản bằng tiếng Anh, nhưng cho lời giải thích tốt đẹp với các ví dụ dễ hiểu. - ivanjovanovic
Big O là ước tính về hiệu suất trường hợp xấu nhất của một hàm giả sử thuật toán sẽ thực hiện số lần lặp tối đa. - Paul Sweatte
Big-O notation explained by a self-taught programmer - Soner Gönül


Các câu trả lời:


Lưu ý nhanh, điều này gần như chắc chắn gây nhầm lẫn Ký hiệu Big O (mà là một ràng buộc trên) với ký hiệu Theta (mà là một ràng buộc hai bên). Theo kinh nghiệm của tôi, điều này thực sự là điển hình của các cuộc thảo luận trong các thiết lập phi học thuật. Xin lỗi vì bất kỳ sự nhầm lẫn nào gây ra.


Độ phức tạp lớn O có thể được hiển thị bằng biểu đồ này:

Big O Analysis

Định nghĩa đơn giản nhất tôi có thể cung cấp cho ký hiệu Big-O là:

Ký hiệu Big-O là biểu diễn tương đối về độ phức tạp của thuật toán.

Có một số từ quan trọng và được lựa chọn có chủ ý trong câu đó:

  • quan hệ: bạn chỉ có thể so sánh táo với táo. Bạn không thể so sánh một thuật toán để làm phép nhân số học cho một thuật toán sắp xếp một danh sách các số nguyên. Nhưng so sánh hai thuật toán để thực hiện phép toán số học (một phép nhân, một phép cộng) sẽ cho bạn biết điều gì đó có ý nghĩa;
  • đại diện: Big-O (ở dạng đơn giản nhất của nó) làm giảm sự so sánh giữa các thuật toán với một biến duy nhất. Biến đó được chọn dựa trên các quan sát hoặc giả định. Ví dụ, các thuật toán sắp xếp thường được so sánh dựa trên các phép so sánh (so sánh hai nút để xác định thứ tự tương đối của chúng). Điều này giả định rằng so sánh là tốn kém. Nhưng nếu so sánh là rẻ nhưng trao đổi thì đắt? Nó thay đổi so sánh; và
  • phức tạp: nếu tôi mất một giây để sắp xếp 10.000 yếu tố thì tôi sẽ mất bao lâu để sắp xếp một triệu? Sự phức tạp trong trường hợp này là một thước đo tương đối với một thứ khác.

Hãy quay lại và đọc lại phần trên khi bạn đã đọc phần còn lại.

Ví dụ tốt nhất của Big-O tôi có thể nghĩ là làm số học. Lấy hai số (123456 và 789012). Các phép tính số học cơ bản mà chúng ta học được ở trường là:

  • thêm vào;
  • phép trừ;
  • phép nhân; và
  • chia.

Mỗi trong số này là một hoạt động hoặc một vấn đề. Một phương pháp giải quyết này được gọi là thuật toán.

Bổ sung là đơn giản nhất. Bạn xếp các con số lên (bên phải) và thêm các chữ số vào cột viết số cuối cùng của phần bổ sung đó trong kết quả. Phần 'hàng chục' của số đó được chuyển sang cột tiếp theo.

Giả sử rằng việc bổ sung những con số này là hoạt động đắt nhất trong thuật toán này. Đó là lý do để thêm hai số này lại với nhau, chúng ta phải cộng lại 6 chữ số (và có thể mang theo số thứ 7). Nếu chúng ta thêm hai số 100 chữ số cùng nhau, chúng ta phải thực hiện thêm 100 số. Nếu chúng ta thêm hai Số lượng 10.000 chữ số, chúng tôi phải thực hiện thêm 10.000 lần bổ sung.

Xem mô hình? Các sự phức tạp (là số lượng hoạt động) tỷ lệ thuận với số chữ số n với số lượng lớn hơn. Chúng tôi gọi đây là Trên) hoặc là độ phức tạp tuyến tính.

Trừ là tương tự (ngoại trừ bạn có thể cần mượn thay vì mang).

Phép nhân là khác nhau. Bạn xếp các con số lên, lấy chữ số đầu tiên ở số dưới cùng và nhân nó lần lượt với mỗi chữ số trong số đầu và cứ thế thông qua từng chữ số. Vì vậy, để nhân hai số có 6 chữ số của chúng tôi, chúng tôi phải thực hiện 36 phép nhân. Chúng tôi có thể cần phải làm nhiều như 10 hoặc 11 cột cho biết thêm để có được kết quả cuối cùng quá.

Nếu chúng ta có hai số có 100 chữ số, chúng ta cần làm 10.000 phép nhân và 200 phép cộng. Đối với hai số một triệu chữ số, chúng tôi cần phải thực hiện một nghìn tỷ (1012) nhân và hai triệu cộng thêm.

Khi thuật toán quy mô với n-bình phương, đây là Trên2) hoặc là bậc hai phức tạp. Đây là thời điểm tốt để giới thiệu một khái niệm quan trọng khác:

Chúng tôi chỉ quan tâm đến phần phức tạp nhất.

Các sắc sảo có thể đã nhận ra rằng chúng tôi có thể thể hiện số lượng các hoạt động như: n2 + 2n. Nhưng như bạn đã thấy từ ví dụ của chúng tôi với hai con số một triệu chữ số, thuật ngữ thứ hai (2n) trở nên không đáng kể (chiếm 0,0002% tổng số hoạt động của giai đoạn đó).

Người ta có thể nhận thấy rằng chúng tôi đã giả định kịch bản trường hợp xấu nhất ở đây. Trong khi nhân các số có 6 chữ số nếu một số có 4 chữ số và số còn lại là 6 chữ số, thì chúng tôi chỉ có 24 số. Tuy nhiên, chúng tôi tính toán kịch bản trường hợp xấu nhất cho 'n' đó, tức là khi cả hai số có 6 chữ số. Do đó ký hiệu Big-O là về kịch bản trường hợp xấu nhất của một thuật toán

Danh bạ điện thoại

Ví dụ tốt nhất tiếp theo mà tôi có thể nghĩ đến là danh bạ điện thoại, thường được gọi là Trang trắng hoặc tương tự nhưng nó sẽ khác nhau giữa các quốc gia. Nhưng tôi đang nói về một trong đó liệt kê những người theo họ và sau đó tắt hoặc tên đầu tiên, có thể địa chỉ và sau đó số điện thoại.

Bây giờ nếu bạn đang hướng dẫn một máy tính tra cứu số điện thoại cho "John Smith" trong danh bạ điện thoại có chứa 1.000.000 tên, bạn sẽ làm gì? Bỏ qua thực tế là bạn có thể đoán được bao xa trong S's bắt đầu (giả sử bạn không thể), bạn sẽ làm gì?

Việc triển khai điển hình có thể là mở cửa ở giữa, lấy 500.000th và so sánh nó với "Smith". Nếu nó xảy ra là "Smith, John", chúng tôi thật sự may mắn. Nhiều khả năng là "John Smith" sẽ ở trước hoặc sau tên đó. Nếu đó là sau khi chúng tôi sau đó chia nửa cuối của danh bạ điện thoại thành một nửa và lặp lại. Nếu trước đó chúng ta chia nửa đầu của cuốn sách điện thoại thành một nửa và lặp lại. Và cứ thế.

Đây được gọi là Tìm kiếm nhị phân và được sử dụng hàng ngày trong lập trình cho dù bạn có nhận ra hay không.

Vì vậy, nếu bạn muốn tìm một tên trong danh bạ một triệu tên, bạn có thể tìm thấy bất kỳ tên nào bằng cách thực hiện điều này nhiều nhất 20 lần. Khi so sánh các thuật toán tìm kiếm, chúng tôi quyết định rằng so sánh này là 'n' của chúng tôi.

  • Đối với một cuốn sách điện thoại của 3 tên nó có 2 so sánh (nhiều nhất).
  • Đối với 7 nó mất nhiều nhất là 3.
  • Đối với 15 phải mất 4.
  • Đối với 1.000.000 phải mất 20.

Đó là đáng kinh ngạc phải không?

Trong điều khoản Big-O, đây là O (log n) hoặc là độ phức tạp lôgarít. Bây giờ logarit trong câu hỏi có thể là ln (base e), log10, nhật ký2 hoặc một số cơ sở khác. Nó không quan trọng nó vẫn là O (log n) giống như O (2n2) và O (100n2) vẫn là cả O (n2).

Thật đáng giá vào thời điểm này để giải thích rằng Big O có thể được sử dụng để xác định ba trường hợp với một thuật toán:

  • Trường hợp tốt nhất: Trong tìm kiếm trong danh bạ điện thoại, trường hợp tốt nhất là chúng tôi tìm thấy tên trong một so sánh. Đây là O (1) hoặc là độ phức tạp liên tục;
  • Trường hợp dự kiến: Như đã thảo luận ở trên đây là O (log n); và
  • Trường hợp xấu nhất: Đây cũng là O (log n).

Thông thường chúng tôi không quan tâm đến trường hợp tốt nhất. Chúng tôi quan tâm đến trường hợp dự kiến ​​và tồi tệ nhất. Đôi khi một hoặc một trong số này sẽ quan trọng hơn.

Quay lại danh bạ điện thoại.

Nếu bạn có số điện thoại và muốn tìm một tên thì sao? Cảnh sát có một cuốn sách điện thoại ngược lại nhưng những cái nhìn như vậy bị từ chối cho công chúng. Hoặc là họ? Về mặt kỹ thuật, bạn có thể đảo ngược tra cứu một số trong một cuốn sách điện thoại thông thường. Làm sao?

Bạn bắt đầu với tên đầu tiên và so sánh số. Nếu đó là một trận đấu, tuyệt vời, nếu không, bạn chuyển sang kế tiếp. Bạn phải làm theo cách này bởi vì danh bạ điện thoại là không có thứ tự (bằng số điện thoại).

Vì vậy, để tìm một tên cho số điện thoại (tra cứu ngược lại):

  • Trường hợp tốt nhất: O (1);
  • Trường hợp dự kiến: O (n) (500.000); và
  • Trường hợp xấu nhất: O (n) (cho 1.000.000).

The Sales Salesman

Đây là một vấn đề khá nổi tiếng trong khoa học máy tính và đáng được đề cập đến. Trong vấn đề này bạn có N thị trấn. Mỗi thị trấn được liên kết với 1 hoặc nhiều thị trấn khác bằng một con đường của một khoảng cách nhất định. Vấn đề Người bán hàng đi du lịch là tìm chuyến đi ngắn nhất đến thăm mọi thị trấn.

Âm thanh đơn giản? Nghĩ lại.

Nếu bạn có 3 thị trấn A, B và C với đường giao thông giữa tất cả các cặp thì bạn có thể đi:

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Thực tế thì có ít hơn vì một số trong số này tương đương nhau (A → B → C và C → B → A là tương đương, ví dụ, vì chúng sử dụng cùng một con đường, ngược lại).

Trong thực tế có 3 khả năng.

  • Đưa nó đến 4 thị trấn và bạn có (iirc) 12 khả năng.
  • Với 5 là 60.
  • 6 trở thành 360.

Đây là hàm của phép toán được gọi là yếu tố. Về cơ bản:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984.000.000
  • 50! = 50 × 49 ×… × 2 × 1 = 3.04140932 × 1064

Vì vậy, Big-O của vấn đề Người bán hàng du lịch là Trên!) hoặc là giai đoạn phức tạp hoặc tổ hợp.

Bởi thời gian bạn nhận được đến 200 thị trấn không có đủ thời gian còn lại trong vũ trụ để giải quyết vấn đề với các máy tính truyền thống.

Đôi điều suy nghĩ.

Thời gian đa thức

Một điểm khác mà tôi muốn đề cập nhanh là bất kỳ thuật toán nào có độ phức tạp Trênmột) được cho là có sự phức tạp đa thức hoặc có thể giải quyết được thời gian đa thức.

O (n), O (n2) vv là tất cả thời gian đa thức. Một số vấn đề không thể được giải quyết trong thời gian đa thức. Một số thứ được sử dụng trên thế giới vì điều này. Mã hóa khóa công khai là một ví dụ điển hình. Thật khó để tính toán hai yếu tố chính của một số rất lớn. Nếu không, chúng tôi không thể sử dụng các hệ thống khóa công khai mà chúng tôi sử dụng.

Dù sao, đó là nó cho lời giải thích của tôi (hy vọng bằng tiếng Anh đơn giản) của Big O (sửa đổi).


6094
2018-01-28 11:18



Trong khi các câu trả lời khác tập trung vào giải thích sự khác biệt giữa O (1), O (n ^ 2) et al .... của bạn là một trong đó chi tiết cách các thuật toán có thể được phân loại thành n ^ 2, nlog (n), vv 1 cho một câu trả lời tốt đã giúp tôi hiểu được ký hiệu Big O - Yew Long
người ta có thể muốn thêm rằng-lớn O đại diện cho một ràng buộc trên (được đưa ra bởi một thuật toán), lớn-Omega cho một ràng buộc thấp hơn (thường được đưa ra như là một bằng chứng độc lập từ một thuật toán cụ thể) và Theta lớn có nghĩa là một thuật toán "tối ưu" đạt được giới hạn dưới đó được biết đến. - mdm
Điều này là tốt nếu bạn đang tìm kiếm câu trả lời dài nhất, nhưng không phải cho câu trả lời giải thích tốt nhất Big-O một cách đơn giản. - kirk.burleson
-1: Điều này hoàn toàn sai: _ "BigOh là đại diện tương đối phức tạp của thuật toán". Không. BigOh là một giới hạn trên tiệm cận và tồn tại khá độc lập với khoa học máy tính. O (n) là tuyến tính. Không, bạn đang bối rối BigOh với theta. log n là O (n). 1 là O (n). Số lượng upvotes để trả lời này (và các ý kiến), mà làm cho những sai lầm cơ bản của khó hiểu Theta với BigOh là khá đáng lo ngại ...
"Bởi thời gian bạn nhận được đến 200 thị trấn không có đủ thời gian còn lại trong vũ trụ để giải quyết vấn đề với các máy tính truyền thống." Khi vũ trụ sắp kết thúc? - Isaac


Nó cho thấy làm thế nào một thuật toán quy mô.

Trên2): được biết như Phức tạp bậc hai

  • 1 mục: 1 giây
  • 10 mục: 100 giây
  • 100 mục: 10000 giây

Lưu ý rằng số lượng mục tăng theo hệ số là 10, nhưng thời gian tăng lên theo hệ số là 102. Về cơ bản, n = 10 và vì vậy O (n2) cung cấp cho chúng tôi hệ số chia tỷ lệ n2 đó là 102.

Trên): được biết như Độ phức tạp tuyến tính

  • 1 mục: 1 giây
  • 10 mục: 10 giây
  • 100 mục: 100 giây

Lần này số lượng vật phẩm tăng thêm 10 lần, và cũng vậy. n = 10 và vì vậy hệ số co giãn của O (n) là 10.

O (1): được biết như Độ phức tạp liên tục

  • 1 mục: 1 giây
  • 10 mục: 1 giây
  • 100 mục: 1 giây

Số lượng các mục vẫn tăng theo hệ số 10, nhưng hệ số tỷ lệ của O (1) luôn là 1.

O (log n): được biết như Độ phức tạp lôgarit

  • 1 mục: 1 giây
  • 10 mục: 2 giây
  • 100 mục: 3 giây
  • 1000 mục: 4 giây
  • 10000 mục: 5 giây

Số lượng tính toán chỉ được tăng lên bằng nhật ký giá trị đầu vào. Vì vậy, trong trường hợp này, giả sử mỗi tính toán mất 1 giây, nhật ký của đầu vào n là thời gian cần thiết, do đó log n.

Đó là ý chính của nó. Chúng giảm toán xuống vì vậy nó có thể không chính xác là n2 hoặc bất cứ điều gì họ nói, nhưng đó sẽ là yếu tố thống trị trong việc mở rộng quy mô.


662
2018-01-28 11:28



định nghĩa này có ý nghĩa gì? (Số lượng các mục vẫn tăng thêm 10 lần, nhưng hệ số tỷ lệ của O (1) luôn là 1.) - HollerTrain
Không phải giây, hoạt động. Ngoài ra, bạn bỏ lỡ thời gian giai thừa và logarit. - Chris Charabaruk
Điều này không giải thích rõ ràng rằng O (n ^ 2) có thể mô tả một thuật toán chạy chính xác .01 * n ^ 2 + 999999 * n + 999999. Điều quan trọng là phải biết rằng các thuật toán được so sánh bằng cách sử dụng thang đo này, và so sánh hoạt động khi n là 'đủ lớn'. Timsort của Python thực sự sử dụng sắp xếp chèn (trường hợp xấu nhất / trung bình O (n ^ 2)) cho các mảng nhỏ do thực tế là nó có một chi phí nhỏ. - Darthfett
Câu trả lời này cũng gây nhầm lẫn ký hiệu O lớn và ký hiệu Theta. Hàm n trả về 1 cho tất cả các đầu vào của nó (thường được viết đơn giản là 1) thực ra là trong O (n ^ 2) (mặc dù nó cũng nằm trong O (1)). Tương tự như vậy, một thuật toán chỉ phải thực hiện một bước mà phải mất một lượng thời gian không đổi cũng được coi là một thuật toán O (1), nhưng cũng là một thuật toán O (n) và O (n ^ 2). Nhưng có lẽ các nhà toán học và các nhà khoa học máy tính không đồng ý về định nghĩa: - /. - Jacob Akkerboom
Các O (log n) Logarithmic phức tạp được coi là trong câu trả lời này là của cơ sở 10. Nói chung tiêu chuẩn là để tính toán với cơ sở 2. Một nên ghi nhớ thực tế này và không nên nhầm lẫn. Cũng như được đề cập bởi @ChrisCharabaruk sự phức tạp biểu thị số lượng hoạt động và không phải giây. - Aksh1801


Ký hiệu Big-O (còn được gọi là ký hiệu "tăng trưởng tiệm cận") những gì có chức năng "giống như" khi bạn bỏ qua các yếu tố không đổi và nội dung gần nguồn gốc. Chúng tôi sử dụng nó để nói về cách quy mô điều.


Khái niệm cơ bản

cho "đủ" đầu vào lớn ...

  • f(x) ∈ O(upperbound) có nghĩa f "phát triển không nhanh hơn" upperbound
  • f(x) ∈ Ɵ(justlikethis) nghĩa là f "phát triển chính xác như" justlikethis
  • f(x) ∈ Ω(lowerbound) có nghĩa f "phát triển không chậm hơn" lowerbound

ký hiệu big-O không quan tâm đến các yếu tố không đổi: hàm 9x² được cho là "phát triển chính xác như" 10x². Không big-O tiệm cận ký hiệu quan tâm về không tiệm cận công cụ ("nội dung gần nguồn gốc" hoặc "điều gì sẽ xảy ra khi kích thước sự cố nhỏ"): chức năng 10x² được cho là "phát triển chính xác như" 10x² - x + 2.

Tại sao bạn muốn bỏ qua các phần nhỏ hơn của phương trình? Bởi vì chúng trở nên hoàn toàn bị lúng túng bởi các phần lớn của phương trình khi bạn xem xét các cân lớn hơn và lớn hơn; đóng góp của họ trở nên lùn và không liên quan. (Xem phần ví dụ.)

Nói cách khác, đó là tất cả về tỉ lệ khi bạn đi đến vô cùng. Nếu bạn chia thời gian thực tế thì O(...), bạn sẽ nhận được một yếu tố không đổi trong giới hạn đầu vào lớn. Trực quan điều này có ý nghĩa: các chức năng "mở rộng như nhau" nếu bạn có thể nhân một với nhau. Đó là, khi chúng ta nói ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... điều này có nghĩa rằng cho các kích thước "đủ lớn" (nếu chúng ta bỏ qua những thứ gần nguồn gốc), có tồn tại một số hằng số (ví dụ: 2,5, được tạo thành hoàn toàn) sao cho:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Có nhiều sự lựa chọn của hằng số; thường thì lựa chọn "tốt nhất" được gọi là "yếu tố không đổi" của thuật toán ... nhưng chúng ta thường bỏ qua nó như chúng ta bỏ qua các thuật ngữ không lớn nhất (xem phần Yếu tố không đổi vì lý do tại sao chúng không quan trọng). Bạn cũng có thể nghĩ về phương trình trên như là một ràng buộc, nói rằng "Trong trường hợp xấu nhất, thời gian cần thiết sẽ không bao giờ tệ hơn khoảng N*log(N), trong hệ số 2.5 (một yếu tố không đổi, chúng tôi không quan tâm nhiều)".

Nói chung, O(...) là cách hữu ích nhất vì chúng ta thường quan tâm đến hành vi xấu nhất. Nếu f(x) đại diện cho một cái gì đó "xấu" như xử lý hoặc sử dụng bộ nhớ, sau đó "f(x) ∈ O(upperbound)" có nghĩa "upperbound là trường hợp xấu nhất của việc sử dụng bộ nhớ / bộ nhớ ".


Các ứng dụng

Là một cấu trúc toán học thuần túy, ký hiệu big-O không bị giới hạn khi nói về thời gian xử lý và bộ nhớ. Bạn có thể sử dụng nó để thảo luận về sự tiệm cận của bất cứ điều gì trong đó mở rộng quy mô có ý nghĩa, chẳng hạn như:

  • số lượng có thể bắt tay giữa N người ở một bữa tiệc (Ɵ(N²), đặc biệt N(N-1)/2, nhưng điều quan trọng là nó "quy mô như" )
  • dự đoán số lượng người dự kiến ​​đã nhìn thấy một số tiếp thị lan truyền như là một hàm của thời gian
  • cách độ trễ của trang web với số lượng đơn vị xử lý trong CPU hoặc GPU hoặc cụm máy tính
  • làm thế nào nhiệt lượng đầu ra quy mô trên CPU chết như là một chức năng của số transistor, điện áp, vv
  • bao nhiêu thời gian một thuật toán cần chạy, như một hàm của kích thước đầu vào
  • bao nhiêu không gian một thuật toán cần phải chạy, như một hàm của kích thước đầu vào

Thí dụ

Đối với ví dụ bắt tay ở trên, mọi người trong phòng lắc tay của mọi người khác. Trong ví dụ đó, #handshakes ∈ Ɵ(N²). Tại sao?

Sao lưu một chút: số lượng bắt tay chính xác là n-chọn-2 hoặc N*(N-1)/2 (mỗi người N bắt tay N-1 người khác, nhưng cái bắt tay hai lần này chia cho 2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Tuy nhiên, đối với số lượng người rất lớn, thuật ngữ tuyến tính N được lùn và có hiệu quả đóng góp 0 cho tỷ lệ (trong biểu đồ: phần của hộp trống trên đường chéo trên tổng số hộp sẽ nhỏ hơn khi số lượng người tham gia trở nên lớn hơn). Do đó, hành vi chia tỷ lệ là order N²hoặc số lượng bắt tay "phát triển như N²".

#handshakes(N)
────────────── ≈ 1/2
     N²

Nó giống như các ô trống trên đường chéo của biểu đồ (N * (N-1) / 2 dấu kiểm) thậm chí không có (N2 dấu kiểm tra tiệm cận).

(Nếu bạn muốn chứng minh điều này cho chính mình, bạn có thể thực hiện một số đại số đơn giản trên tỷ lệ để chia nó thành nhiều thuật ngữ (limcó nghĩa là "được xem xét trong giới hạn", chỉ cần bỏ qua nó nếu bạn không nhìn thấy nó, nó chỉ là ký hiệu cho "và N thực sự thực sự lớn"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Số lượng bắt tay 'trông giống như' x² rất nhiều cho các giá trị lớn, nếu chúng ta viết tỷ lệ # bắt tay / x², thực tế là chúng ta không cần chính xác x² handshakes thậm chí sẽ không hiển thị trong thập phân cho một tùy ý lớn trong khi.

ví dụ. cho x = 1million, tỷ lệ # bắt tay / x²: 0,499999 ...


Xây dựng trực giác

Điều này cho phép chúng tôi đưa ra các tuyên bố như ...

"Đối với đầu vào đủ lớn = N, bất kể yếu tố hằng số là gì, nếu tôi gấp đôi kích thước đầu vào


362
2017-07-08 04:46



Một câu trả lời toán học xuất sắc, nhưng OP đã yêu cầu một câu trả lời bằng tiếng Anh đơn giản. Mức độ mô tả toán học này không bắt buộc phải hiểu câu trả lời, mặc dù đối với những người đặc biệt chú ý về mặt toán học, nó có thể đơn giản hơn rất nhiều để hiểu hơn "tiếng Anh thuần túy". Tuy nhiên, OP yêu cầu sau này. - El Zorko
Có lẽ những người khác ngoài OP có thể quan tâm đến câu trả lời cho câu hỏi này. Đó không phải là nguyên tắc hướng dẫn của trang web phải không? - Casey
Trong khi tôi có thể thấy lý do tại sao mọi người có thể bỏ qua câu trả lời của tôi và nghĩ rằng nó quá toán học (đặc biệt là "toán học là tiếng anh đơn giản mới" nhận xét snide, kể từ khi bị xóa), câu hỏi ban đầu hỏi về big-O đó là về chức năng, vì vậy tôi cố gắng rõ ràng và nói về các chức năng theo cách bổ sung trực giác bằng tiếng Anh. Toán học ở đây thường có thể bị che khuất, hoặc được hiểu với một nền toán học trung học. Tôi cảm thấy rằng mọi người có thể nhìn vào chương trình Math Addenda ở phần cuối, và cho rằng đó là một phần của câu trả lời, khi nó chỉ đơn thuần ở đó để xem thực toán học trông giống như. - ninjagecko
Đây là một câu trả lời tuyệt vời; IMO tốt hơn nhiều so với IMO nhiều nhất. Yêu cầu "toán học" không vượt quá những gì cần thiết để hiểu các biểu thức trong dấu ngoặc đơn sau "O", không có giải thích hợp lý nào sử dụng bất kỳ ví dụ nào có thể tránh được. - Dave Abrahams
"f (x) ∈ O (upperbound) có nghĩa là f" không phát triển nhanh hơn "upperbound" ba từ này đơn giản, nhưng giải thích đúng về mặt toán học của Oh, Theta và Omega lớn là vàng. Ông mô tả cho tôi bằng tiếng Anh đơn giản rằng 5 nguồn khác nhau dường như không thể dịch sang tôi mà không viết các biểu thức toán học phức tạp. Cảm ơn người đàn ông! :) - timbram


EDIT: Ghi chú nhanh, điều này gần như chắc chắn gây nhầm lẫn Ký hiệu Big O (mà là một ràng buộc trên) với ký hiệu Theta (mà là cả một ràng buộc trên và dưới). Theo kinh nghiệm của tôi, điều này thực sự là điển hình của các cuộc thảo luận trong các thiết lập phi học thuật. Xin lỗi vì bất kỳ sự nhầm lẫn nào gây ra.

Trong một câu: Khi quy mô công việc của bạn tăng lên, mất bao nhiêu thời gian để hoàn thành nó?

Rõ ràng đó là chỉ sử dụng "kích thước" như đầu vào và "thời gian thực hiện" như đầu ra - ý tưởng tương tự áp dụng nếu bạn muốn nói về việc sử dụng bộ nhớ, v.v.

Đây là một ví dụ mà chúng tôi có N áo phông mà chúng tôi muốn sấy khô. Tốt giả định nó cực kỳ nhanh chóng để có được chúng ở vị trí sấy khô (tức là sự tương tác của con người là không đáng kể). Đó không phải là trường hợp trong cuộc sống thực, tất nhiên ...

  • Sử dụng một dây chuyền giặt bên ngoài: giả sử bạn có một sân sau lớn vô cùng, giặt khô trong thời gian O (1). Tuy nhiên nhiều bạn có nó, nó sẽ có được cùng một mặt trời và không khí trong lành, vì vậy kích thước không ảnh hưởng đến thời gian khô.

  • Sử dụng máy sấy quần áo: bạn đặt 10 áo sơ mi trong mỗi lần tải, và sau đó chúng được thực hiện một giờ sau đó. (Bỏ qua những con số thực tế ở đây - chúng không liên quan.) Vì vậy, hãy sấy 50 chiếc áo sơ mi trong khoảng 5 lần miễn là sấy 10 áo sơ mi.

  • Đặt tất cả mọi thứ trong một tủ phát sóng: Nếu chúng tôi đặt tất cả mọi thứ trong một đống lớn và chỉ để cho sự ấm áp chung làm điều đó, nó sẽ mất một thời gian dài cho các áo sơ mi trung bình để có được khô. Tôi không muốn đoán chi tiết, nhưng tôi nghi ngờ đây là ít nhất O (N ^ 2) - khi bạn tăng tải giặt, thời gian sấy tăng nhanh hơn.

Một khía cạnh quan trọng của ký hiệu "big O" là nó không nói thuật toán nào sẽ nhanh hơn cho một kích thước nhất định. Có một hashtable (chuỗi khóa, giá trị số nguyên) vs một mảng các cặp (chuỗi, số nguyên). Tìm nhanh khóa trong phần tử bắt đầu hoặc phần tử trong mảng có nhanh hơn không, dựa trên chuỗi? (ví dụ cho mảng, "tìm phần tử đầu tiên trong đó phần chuỗi khớp với khóa đã cho.") Hashtables thường được khấu hao (~ = "trung bình") O (1) - khi chúng được thiết lập, nó sẽ mất khoảng đồng thời để tìm một mục nhập trong một bảng nhập 100 như trong bảng nhập 1.000.000. Tìm một phần tử trong một mảng (dựa trên nội dung thay vì chỉ mục) là tuyến tính, tức là O (N) - trung bình, bạn sẽ phải xem xét một nửa các mục.

Điều này làm cho một hashtable nhanh hơn một mảng cho tra cứu? Không cần thiết. Nếu bạn có một bộ sưu tập rất nhỏ các mục, một mảng có thể nhanh hơn - bạn có thể kiểm tra tất cả các chuỗi trong thời gian cần để tính toán mã băm của mã bạn đang xem. Tuy nhiên, khi tập dữ liệu phát triển lớn hơn, thì hashtable cuối cùng sẽ đánh bại mảng.


237
2018-01-28 11:16



Một hashtable yêu cầu một thuật toán để chạy để tính toán chỉ số của mảng thực tế (tùy thuộc vào việc thực hiện). Và một mảng chỉ có O (1) bởi vì nó chỉ là một địa chỉ. Nhưng điều này không liên quan gì đến câu hỏi, chỉ là quan sát :) - Filip Ekberg
Lời giải thích của jon có rất nhiều việc phải làm với câu hỏi tôi nghĩ. đó chính xác là cách người ta có thể giải thích nó cho một số bà mẹ, và cuối cùng cô ấy sẽ hiểu nó tôi nghĩ :) tôi thích ví dụ quần áo (đặc biệt là cuối cùng, nơi nó giải thích sự tăng trưởng theo cấp số nhân của sự phức tạp) - Johannes Schaub - litb
Filip: Tôi không nói về địa chỉ một mảng theo chỉ mục, tôi đang nói về việc tìm kiếm một mục phù hợp trong một mảng. Bạn có thể đọc lại câu trả lời và xem liệu câu trả lời đó vẫn chưa rõ ràng? - Jon Skeet
@ Filip Ekberg Tôi nghĩ rằng bạn đang nghĩ đến một bảng địa chỉ trực tiếp, nơi mỗi chỉ mục ánh xạ tới một khóa trực tiếp do đó là O (1), tuy nhiên tôi tin Jon đang nói về một mảng chưa được sắp xếp của các cặp khóa / val mà bạn phải tìm kiếm thông qua tuyến tính. - ljs
@ RBT: Không, nó không phải là một tra cứu nhị phân. Nó có thể đến đúng băm cái xô ngay lập tức, chỉ dựa trên chuyển đổi từ mã băm thành chỉ mục nhóm. Sau đó, việc tìm đúng mã băm trong thùng có thể là tuyến tính hoặc nó có thể là tìm kiếm nhị phân ... nhưng vào thời điểm đó bạn sẽ giảm xuống một tỷ lệ rất nhỏ trong tổng kích thước của từ điển. - Jon Skeet


Big O mô tả một giới hạn trên về hành vi tăng trưởng của một hàm, ví dụ như thời gian chạy của một chương trình, khi đầu vào trở nên lớn.

Ví dụ:

  • O (n): Nếu tôi tăng gấp đôi kích thước đầu vào, thời gian chạy gấp đôi

  • Trên2): Nếu kích thước đầu vào tăng gấp đôi quadruples thời gian chạy

  • O (log n): Nếu kích thước đầu vào tăng gấp đôi thời gian chạy tăng lên một

  • O (2n): Nếu kích thước đầu vào tăng lên một, thời gian chạy đôi

Kích thước đầu vào thường là không gian theo bit cần thiết để biểu diễn đầu vào.


120
2018-01-28 11:23



sai! ví dụ O (n): Nếu tôi tăng gấp đôi kích thước đầu vào, thời gian chạy sẽ nhân với số không không đổi hữu hạn. Ý tôi là O (n) = O (n + n) - arena-ru
Tôi đang nói về f trong f (n) = O (g (n)), không phải là g như bạn có vẻ hiểu. - starblue
Tôi upvoted, nhưng câu cuối cùng không đóng góp nhiều tôi cảm thấy. Chúng ta thường không nói về "bit" khi thảo luận hoặc đo lường Big (O). - cdiggins
Bạn nên thêm một ví dụ cho O (n log n). - Christoffer Hammarström
Đó không phải là quá rõ ràng, về cơ bản nó hoạt động tồi tệ hơn một chút so với O (n). Vì vậy, nếu n tăng gấp đôi, thời gian chạy được nhân với một yếu tố lớn hơn 2. - starblue


Ký hiệu Big O thường được sử dụng bởi các lập trình viên như một thước đo gần đúng về độ dài của phép tính (thuật toán) để hoàn thành được biểu diễn như một hàm của kích thước của bộ đầu vào.

Big O rất hữu ích khi so sánh hai thuật toán sẽ tăng lên khi số lượng đầu vào tăng lên.

Chính xác hơn Ký hiệu Big O được sử dụng để thể hiện hành vi tiệm cận của một hàm. Điều đó có nghĩa là hàm hoạt động như thế nào khi nó tiến tới vô cùng.

Trong nhiều trường hợp, "O" của thuật toán sẽ rơi vào một trong các trường hợp sau:

  • O (1) - Thời gian hoàn thành là như nhau bất kể kích thước của bộ đầu vào. Một ví dụ là truy cập một phần tử mảng theo chỉ mục.
  • O (Nhật ký N) - Thời gian để hoàn thành tăng gần đúng với log2 (n). Ví dụ 1024 mục mất khoảng hai lần miễn là 32 mục, vì Log2 (1024) = 10 và Log2 (32) = 5. Ví dụ là tìm một mục trong một cây tìm kiếm nhị phân (BST).
  • TRÊN) - Thời gian để hoàn thành quy mô tuyến tính với kích thước của bộ đầu vào. Nói cách khác, nếu bạn tăng gấp đôi số lượng các mục trong tập hợp đầu vào, thuật toán mất khoảng gấp đôi thời gian. Một ví dụ là đếm số lượng các mục trong một danh sách liên kết.
  • O (N Log N) - Thời gian để hoàn thành tăng theo số lượng các mục lần kết quả của Log2 (N). Một ví dụ về điều này là đống phân loại và sắp xếp nhanh chóng.
  • O (N ^ 2) - Thời gian hoàn thành tương đương với bình phương của số lượng mục. Một ví dụ về điều này là bong bóng sắp xếp.
  • TRÊN!) - Thời gian hoàn thành là giai thừa của tập hợp đầu vào. Một ví dụ về điều này là đi du lịch nhân viên bán hàng vấn đề brute-lực lượng giải pháp.

Big O bỏ qua các yếu tố không đóng góp một cách có ý nghĩa vào đường cong tăng trưởng của hàm khi kích thước đầu vào tăng lên theo hướng vô cùng. Điều này có nghĩa là các hằng số được thêm vào hoặc nhân với hàm chỉ bị bỏ qua.


97
2017-09-05 16:31



cdiggins, nếu tôi có O (N / 2) phức tạp, nó phải là O (N) hoặc O (N / 2), ví dụ như những gì phức tạp nếu tôi sẽ lặp hơn một nửa chuỗi. - Melad Ezzat
@Melad Đây là một ví dụ về hằng số (0,5) được nhân với hàm. Điều này bị bỏ qua vì nó được coi là có tác dụng có ý nghĩa đối với các giá trị rất lớn của N. - cdiggins


Big O chỉ là một cách để "thể hiện" bản thân theo cách thông thường, "Mất bao nhiêu thời gian / không gian để chạy mã của tôi?".

Bạn có thể thường thấy O (n), O (n2), O (nlogn) và vv, tất cả những điều này chỉ là những cách để thể hiện; Thuật toán thay đổi như thế nào?

O (n) có nghĩa là Big O là n, và bây giờ bạn có thể nghĩ, "N là gì !?" Vâng "n" là số lượng các phần tử. Hình ảnh bạn muốn tìm kiếm một Item trong một mảng. Bạn sẽ phải xem từng phần tử và "Bạn có phải là yếu tố / mục đúng không?" trong trường hợp xấu nhất, mục nằm ở chỉ mục cuối cùng, có nghĩa là mất nhiều thời gian vì có các mục trong danh sách, do đó, để chung chung, chúng tôi nói "oh hey, n là số tiền hợp lý cho các giá trị!" .

Vì vậy, sau đó bạn có thể hiểu những gì "n2"có nghĩa là, nhưng để cụ thể hơn, hãy chơi với ý nghĩ bạn có một đơn giản, thuật toán phân loại đơn giản nhất; bubbleort. Thuật toán này cần xem xét toàn bộ danh sách, cho mỗi mục.

Danh sách của tôi

  1. 1
  2. 6
  3. 3

Dòng chảy ở đây sẽ là:

  • So sánh 1 và 6, cái nào lớn nhất? Ok 6 ở đúng vị trí, tiến lên phía trước!
  • So sánh 6 và 3, oh, 3 là ít hơn! Hãy di chuyển điều đó, Ok danh sách thay đổi, chúng ta cần phải bắt đầu từ đầu bây giờ!

Đây là O n2 bởi vì, bạn cần xem tất cả các mục trong danh sách có các mục "n". Đối với mỗi mục, bạn nhìn vào tất cả các mục một lần nữa, để so sánh, đây cũng là "n", vì vậy đối với mỗi mục, bạn nhìn "n" lần n * n = n2

Tôi hy vọng điều này đơn giản như bạn muốn.

Nhưng hãy nhớ rằng, Big O chỉ là một cách để vươn lên theo cách của thời gian và không gian.


77
2018-01-28 11:14



cho logN chúng ta xem xét cho vòng lặp chạy từ 0 đến N / 2 những gì về O (log log N)? Ý tôi là chương trình trông như thế nào? tha thứ cho tôi về kỹ năng toán thuần túy - Pablo Escobar


Big O mô tả bản chất tỉ lệ cơ bản của một thuật toán.

Có rất nhiều thông tin mà Big O không cho bạn biết về một thuật toán đã cho. Nó cắt thành xương và chỉ cung cấp thông tin về tính chất mở rộng của thuật toán, cụ thể cách sử dụng tài nguyên (suy nghĩ thời gian hoặc bộ nhớ) của một thuật toán quy mô để đáp ứng với "kích thước đầu vào".

Hãy xem xét sự khác biệt giữa một động cơ hơi nước và một tên lửa. Chúng không chỉ đơn thuần là giống khác nhau của cùng một thứ (như, nói, một động cơ Prius so với động cơ Lamborghini) nhưng chúng là các loại hệ thống đẩy khác nhau đáng kể, ở cốt lõi của chúng. Một động cơ hơi nước có thể nhanh hơn tên lửa đồ chơi, nhưng không có động cơ piston hơi nước nào có thể đạt được tốc độ của một chiếc xe khởi động quỹ đạo. Điều này là do các hệ thống này có các đặc điểm nhân rộng khác nhau liên quan đến mối quan hệ của nhiên liệu cần thiết ("sử dụng tài nguyên") để đạt được tốc độ nhất định ("kích thước đầu vào").

Tại sao cái này lại quan trọng đến vậy? Bởi vì phần mềm đề cập đến các vấn đề có thể khác về kích thước bởi các yếu tố lên đến một nghìn tỷ. Hãy cân nhắc điều đó một lúc. Tỷ lệ giữa tốc độ cần thiết để di chuyển đến Mặt trăng và tốc độ đi bộ của con người nhỏ hơn 10.000: 1 và điều đó hoàn toàn nhỏ so với phạm vi trong phần mềm kích cỡ đầu vào có thể phải đối mặt. Và bởi vì phần mềm có thể phải đối mặt với phạm vi thiên văn trong kích thước đầu vào, nên tiềm năng cho độ phức tạp của thuật toán Big O, đó là tính chất mở rộng cơ bản, để vượt qua mọi chi tiết triển khai.

Hãy xem xét ví dụ phân loại kinh điển. Sắp xếp bong bóng là O (n2) trong khi phối hợp sắp xếp là O (n log n). Giả sử bạn có hai ứng dụng sắp xếp, ứng dụng A sử dụng phân loại bong bóng và ứng dụng B sử dụng sắp xếp hợp nhất và giả sử rằng kích thước đầu vào khoảng 30 phần tử ứng dụng A nhanh hơn ứng dụng B gấp 1000 lần. Nếu bạn không bao giờ phải sắp xếp nhiều hơn 30 phần tử thì rõ ràng là bạn nên thích ứng dụng A, vì các kích thước đầu vào này nhanh hơn nhiều. Tuy nhiên, nếu bạn thấy rằng bạn có thể phải sắp xếp mười triệu mục thì điều bạn mong đợi là ứng dụng B thực sự kết thúc nhanh hơn hàng nghìn lần so với ứng dụng A trong trường hợp này, hoàn toàn do cách mà mỗi thuật toán co lại.


52
2018-01-28 13:12





Đây là đồng tiền tiếng Anh đơn giản mà tôi thường sử dụng khi giải thích các giống phổ biến của Big-O

Trong mọi trường hợp, thích các thuật toán cao hơn trong danh sách cho những thuật toán thấp hơn trong danh sách. Tuy nhiên, chi phí chuyển sang một lớp phức tạp đắt tiền khác nhau đáng kể.

O (1):

Không tăng trưởng. Bất kể vấn đề lớn như thế nào, bạn có thể giải quyết nó trong cùng một khoảng thời gian. Điều này là tương tự như phát sóng, nơi nó có cùng một lượng năng lượng để phát sóng trên một khoảng cách nhất định, bất kể số lượng người nằm trong phạm vi phát sóng.

O (nhật ký n):

Sự phức tạp này giống như O (1) ngoại trừ việc nó tồi tệ hơn một chút. Đối với tất cả các mục đích thực tế, bạn có thể coi đây là một quy mô không đổi rất lớn. Sự khác biệt trong công việc giữa việc xử lý 1 nghìn và 1 tỷ mục chỉ là một nhân tố thứ sáu.

O (n):

Chi phí giải quyết vấn đề tỷ lệ thuận với kích thước của vấn đề. Nếu vấn đề của bạn tăng gấp đôi, thì chi phí của giải pháp tăng gấp đôi. Vì hầu hết các vấn đề phải được quét vào máy tính theo một cách nào đó, như nhập dữ liệu, đọc đĩa hoặc lưu lượng mạng, đây thường là yếu tố mở rộng hợp lý.

O (n nhật ký n):

Sự phức tạp này rất giống với O (n). Đối với tất cả các mục đích thực tế, cả hai đều tương đương nhau. Mức độ phức tạp này nói chung vẫn được coi là có thể mở rộng. Bằng cách tinh chỉnh các giả định một số O (n nhật ký n) các thuật toán có thể được chuyển đổi thành O (n) thuật toán. Ví dụ: giới hạn kích thước của các phím sẽ giảm phân loại từ O (n nhật ký n) đến O (n).

O (n2):

Phát triển thành hình vuông, nơi n là chiều dài cạnh của hình vuông. Đây là tốc độ tăng trưởng tương tự như "hiệu ứng mạng", nơi mọi người trong mạng có thể biết mọi người khác trong mạng. Tăng trưởng là tốn kém. Hầu hết các giải pháp có thể mở rộng không thể sử dụng các thuật toán với mức độ phức tạp này mà không thực hiện các hoạt động thể dục đáng kể. Điều này thường áp dụng cho tất cả các phức tạp đa thức khác - O (nk) - cũng.

O (2n):

Không quy mô. Bạn không có hy vọng giải quyết bất kỳ vấn đề nào không tầm thường. Hữu ích khi biết những gì cần tránh và để các chuyên gia tìm các thuật toán gần đúng có trong O (nk).


35
2018-01-27 23:09



Bạn có thể vui lòng xem xét một tương tự khác nhau cho O (1)? Các kỹ sư trong tôi muốn kéo ra một cuộc thảo luận về trở kháng RF do vật cản. - johnwbyrd
Tôi đã sử dụng từ "hơi" vì lý do chính đáng. - Andrew Prock


Big O là thước đo bao nhiêu thời gian / không gian mà thuật toán sử dụng tương đối so với kích thước đầu vào của nó.

Nếu một thuật toán là O (n) thì thời gian / không gian sẽ tăng với cùng tốc độ như đầu vào của nó.

Nếu một thuật toán là O (n2) thì thời gian / không gian tăng theo tỷ lệ đầu vào bình phương của nó.

và vân vân.


34
2018-01-28 11:19



Nó không phải về không gian. Đó là về sự phức tạp có nghĩa là thời gian. - S.Lott
Tôi luôn tin rằng nó có thể là khoảng thời gian HOẶC không gian. nhưng không phải về cả hai cùng một lúc. - Rocco
Sự phức tạp chắc chắn nhất có thể là về không gian. Có một cái nhìn tại đây: en.wikipedia.org/wiki/PSPACE - Tom Crockett
Câu trả lời này là câu trả lời "đơn giản nhất" ở đây. Những người trước đây thực sự cho rằng độc giả biết đủ để hiểu họ nhưng người viết không nhận thức được điều đó. Họ nghĩ rằng họ là đơn giản và đồng bằng, đó là hoàn toàn không. Viết một văn bản rất nhiều với định dạng đẹp và làm cho các ví dụ nhân tạo ưa thích mà khó để không CS người không phải là đồng bằng và đơn giản, nó chỉ là hấp dẫn đối với stackoverflowers người chủ yếu là CS để bỏ phiếu. Giải thích thuật ngữ CS trong tiếng Anh đơn giản không cần gì về mã và toán. 1 cho câu trả lời này mặc dù nó vẫn chưa đủ tốt. - W.Sun
Câu trả lời này làm cho lỗi (phổ biến) giả định rằng f = O (g) có nghĩa là f và g là tỷ lệ thuận. - Paul Hankin


Rất khó để đo tốc độ của các chương trình phần mềm, và khi chúng ta thử, các câu trả lời có thể rất phức tạp và đầy những ngoại lệ và các trường hợp đặc biệt. Đây là một vấn đề lớn, bởi vì tất cả những trường hợp ngoại lệ và trường hợp đặc biệt đó đều gây mất tập trung và vô ích khi chúng ta muốn so sánh hai chương trình khác nhau với nhau để tìm ra cái nào là "nhanh nhất".

Kết quả của sự phức tạp vô ích này, mọi người cố gắng mô tả tốc độ của các chương trình phần mềm bằng cách sử dụng các biểu thức nhỏ nhất và ít phức tạp nhất (toán học) có thể. Những biểu thức này rất gần đúng: Mặc dù, với một chút may mắn, chúng sẽ nắm bắt được "bản chất" của một phần mềm nhanh hay chậm.

Bởi vì chúng xấp xỉ, chúng ta sử dụng chữ "O" (Big Oh) trong biểu thức, như một quy ước để báo hiệu cho người đọc rằng chúng ta đang tạo ra một sự đơn giản hóa tổng thể. (Và để chắc chắn rằng không ai lầm tưởng rằng biểu thức đó là bất kỳ cách nào chính xác).

Nếu bạn đọc "Oh" như ý nghĩa "theo thứ tự" hoặc "xấp xỉ", bạn sẽ không đi quá xa sai. (Tôi nghĩ sự lựa chọn của Big-Oh có thể là một nỗ lực hài hước).

Điều duy nhất mà các biểu thức "Big-Oh" cố gắng làm là mô tả phần mềm sẽ chậm lại như thế nào khi chúng tôi tăng lượng dữ liệu mà phần mềm phải xử lý. Nếu chúng ta tăng gấp đôi lượng dữ liệu cần được xử lý, phần mềm có cần gấp đôi thời gian để hoàn thành công việc không? Mười lần bao lâu? Trong thực tế, có một số lượng rất lớn các biểu thức lớn-Oh mà bạn sẽ gặp phải và cần phải lo lắng về:

Tốt:

  • O(1)  Không thay đổi: Chương trình mất cùng thời gian để chạy bất kể đầu vào lớn như thế nào.
  • O(log n)  Lôgarít: Thời gian chạy chương trình chỉ tăng chậm, ngay cả với mức tăng lớn về kích thước của đầu vào.

Những người xấu:

  • O(n)  Tuyến tính: Thời gian chạy chương trình tăng tương ứng với kích thước của đầu vào.
  • O(n^k)  Đa thức: - Thời gian xử lý phát triển nhanh hơn và nhanh hơn - như một hàm đa thức - khi kích thước của đầu vào tăng lên.

... và xấu xí:

  • O(k^n)  số mũ Thời gian chạy chương trình tăng rất nhanh với mức tăng vừa phải về kích thước của vấn đề - nó chỉ thực tế để xử lý các tập dữ liệu nhỏ với các thuật toán mũ.
  • O(n!)  yếu tố Thời gian chạy chương trình sẽ dài hơn bạn có thể đủ khả năng để chờ đợi bất cứ điều gì, nhưng các bộ dữ liệu nhỏ nhất và tầm thường nhất.

30
2018-05-29 13:51



Tôi cũng đã nghe thuật ngữ Linearithmic - O(n log n) mà sẽ được coi là tốt. - Jason Down