Câu hỏi O (log n) có nghĩa là gì?


Tôi hiện đang tìm hiểu về thời gian chạy Big O Notation và thời gian phân bổ. Tôi hiểu khái niệm về Trên) thời gian tuyến tính, có nghĩa là kích thước của đầu vào ảnh hưởng đến sự tăng trưởng của thuật toán theo tỷ lệ ... và tương tự, ví dụ, thời gian bậc hai Trên2) v..v .. cả các thuật toán, chẳng hạn như máy tạo hoán vị, với Trên!) thời gian, mà phát triển bởi giai thừa.

Ví dụ, hàm sau đây là Trên) bởi vì thuật toán tăng theo tỉ lệ đầu vào của thuật toán n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Tương tự, nếu có một vòng lặp lồng nhau, thời gian sẽ là O (n2).

Nhưng chính xác thì O (log n)? Ví dụ, có nghĩa là gì để nói rằng chiều cao của một cây nhị phân hoàn thành là O (log n)?

Tôi biết (có thể không chi tiết lắm) Logarithm là gì, theo nghĩa là: log10 100 = 2, nhưng tôi không thể hiểu cách xác định hàm có thời gian lôgarit.


1736
2018-02-21 20:05


gốc


Cây nhị phân 1-nút có chiều cao log2 (1) +1 = 1, cây 2 nút có chiều cao log2 (2) +1 = 2, cây 4 nút có chiều cao log2 (4) +1 = 3 và Sớm. Cây n-nút có chiều cao log2 (n) +1, vì vậy việc thêm các nút vào cây làm chiều cao trung bình của nó tăng trưởng logarit. - David R Tribble
Một điều tôi thấy trong hầu hết các câu trả lời là về cơ bản chúng mô tả "O (cái gì đó)" có nghĩa là thời gian chạy của thuật toán tăng theo tỷ lệ "cái gì đó". Cho rằng bạn đã yêu cầu "ý nghĩa chính xác" của "O (log n)", điều đó không đúng. Đó là mô tả trực quan về ký hiệu Big-Theta, chứ không phải Big-O. O (log n) trực giác nghĩa là thời gian chạy tăng lên nhất tỷ lệ thuận với "log n": stackoverflow.com/questions/471199/… - Mehrdad Afshari
Tôi luôn luôn nhớ chia và chinh phục làm ví dụ cho O (log n) - RichardOD
Điều quan trọng là nhận ra rằng cơ sở log 2 của nó (không phải cơ số 10). Điều này là do tại mỗi bước trong thuật toán, bạn loại bỏ một nửa số lựa chọn còn lại của mình. Trong khoa học máy tính, chúng ta hầu như luôn đối phó với log 2 bởi vì chúng ta có thể bỏ qua các hằng số. Tuy nhiên, có một số ngoại lệ (tức là thời gian chạy của Quad Tree là cơ sở nhật ký 4) - Ethan
@Ethan: Nó không quan trọng mà bạn đang ở trong cơ sở, kể từ khi chuyển đổi cơ sở chỉ là một phép nhân liên tục, Công thức là log_b (x) = log_d (x) / log_d (b). Log_d (b) sẽ chỉ là một hằng số. - mindvirus


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


Tôi không thể hiểu làm thế nào để xác định một chức năng với một thời gian đăng nhập.

Các thuộc tính phổ biến nhất của hàm thời gian chạy logarit là:

  • lựa chọn yếu tố tiếp theo để thực hiện một số hành động là một trong nhiều khả năng và
  • chỉ một người sẽ cần phải được chọn.

hoặc là

  • các yếu tố mà hành động được thực hiện là các chữ số của n

Đây là lý do tại sao, ví dụ, tìm kiếm người trong sổ điện thoại là O (log n). Bạn không cần phải kiểm tra mỗi người trong sổ điện thoại để tìm đúng người; thay vào đó, bạn có thể chỉ cần phân chia và chinh phục bằng cách tìm kiếm dựa trên tên của chúng theo thứ tự bảng chữ cái và trong mỗi phần bạn chỉ cần khám phá một tập hợp con của từng phần trước khi bạn tìm thấy số điện thoại của ai đó.

Tất nhiên, một cuốn sách điện thoại lớn hơn vẫn sẽ đưa bạn một thời gian dài hơn, nhưng nó sẽ không phát triển nhanh như sự gia tăng tỷ lệ thuận với kích thước bổ sung.


Chúng tôi có thể mở rộng ví dụ về danh bạ điện thoại để so sánh các loại hoạt động khác và của chúng thời gian chạy. Chúng tôi sẽ giả định cuốn sách điện thoại của chúng tôi có các doanh nghiệp ("Trang vàng") có tên duy nhất và những người ("Trang trắng") có thể không có tên duy nhất. Số điện thoại được gán cho tối đa một người hoặc doanh nghiệp. Chúng tôi cũng giả định rằng phải mất thời gian không đổi để lật đến một trang cụ thể.

Dưới đây là thời gian hoạt động của một số hoạt động chúng tôi có thể thực hiện trên danh bạ điện thoại, từ tốt nhất đến tồi tệ nhất:

  • O (1) (trường hợp tốt nhất): Với trang của tên doanh nghiệp và tên doanh nghiệp, hãy tìm số điện thoại.

  • O (1) (trường hợp trung bình): Với trang mà tên của một người đang bật và tên của họ, hãy tìm số điện thoại.

  • O (log n): Đặt tên cho một người, tìm số điện thoại bằng cách chọn một điểm ngẫu nhiên khoảng nửa chừng của cuốn sách bạn chưa tìm kiếm, sau đó kiểm tra xem liệu tên của người đó có ở thời điểm đó hay không. Sau đó lặp lại quá trình này ở nửa chừng của cuốn sách nơi tên của người đó nằm. (Đây là tìm kiếm nhị phân cho tên của một người.)

  • Trên): Tìm tất cả những người có số điện thoại chứa chữ số "5".

  • Trên): Được cung cấp số điện thoại, tìm người hoặc doanh nghiệp có số đó.

  • O (n log n): Có một sự pha trộn tại văn phòng máy in, và danh bạ điện thoại của chúng tôi có tất cả các trang được chèn vào theo thứ tự ngẫu nhiên. Sửa chữa thứ tự sao cho nó đúng bằng cách nhìn vào tên đầu tiên trên mỗi trang và sau đó đặt trang đó vào vị trí thích hợp trong một sổ điện thoại mới, trống.

Đối với các ví dụ dưới đây, chúng tôi hiện đang ở văn phòng của máy in. Sổ điện thoại đang chờ để được gửi đến từng cư dân hoặc doanh nghiệp, và có một nhãn dán trên mỗi cuốn danh bạ điện thoại để xác định nơi nó sẽ được gửi đến. Mọi người hoặc doanh nghiệp đều có một danh bạ điện thoại.

  • O (n log n): Chúng tôi muốn cá nhân hóa sổ điện thoại, vì vậy chúng tôi sẽ tìm tên của từng người hoặc doanh nghiệp trong bản sao được chỉ định của họ, sau đó khoanh tròn tên của họ trong sách và viết một lời cảm ơn ngắn cho sự bảo trợ của họ.

  • Trên2): Đã xảy ra lỗi tại văn phòng và mọi mục nhập trong mỗi cuốn sách điện thoại đều có thêm "0" ở cuối số điện thoại. Lấy một số màu trắng ra và loại bỏ từng số không.

  • O (n · n!): Chúng tôi đã sẵn sàng để tải danh bạ vào dock vận chuyển. Thật không may, những robot được cho là để tải những cuốn sách đã đi haywire: nó đặt những cuốn sách lên xe tải theo một thứ tự ngẫu nhiên! Thậm chí tệ hơn, nó tải tất cả các sách lên xe tải, sau đó kiểm tra xem chúng có đúng thứ tự không, và nếu không, nó sẽ dỡ chúng ra và bắt đầu lại. (Đây là nỗi sợ hãi bogo sắp xếp.)

  • Trênn): Bạn sửa chữa robot để nó tải mọi thứ một cách chính xác. Ngày hôm sau, một trong những đồng nghiệp của bạn chơi trò đùa với bạn và nối dây chuyền tải dock robot với hệ thống in tự động. Mỗi khi robot đi để tải một cuốn sách gốc, máy in của nhà máy làm cho một bản sao chạy của tất cả các danh bạ! May mắn thay, hệ thống phát hiện lỗi của robot đủ tinh vi để robot không thử in nhiều bản sao hơn khi nó gặp một cuốn sách trùng lặp để tải, nhưng nó vẫn phải tải mọi cuốn sách gốc và bản sao được in.


2182
2018-02-21 20:14



@cletus: Trùng hợp, tôi sợ. Tôi đã chọn nó vì danh bạ có một chữ N lớn, mọi người hiểu chúng là gì và chúng làm gì, và vì nó linh hoạt như một ví dụ. Cộng với tôi đã sử dụng robot trong lời giải thích của tôi! Một chiến thắng xung quanh. (Ngoài ra, có vẻ như câu trả lời của bạn đã được thực hiện trước khi tôi còn là thành viên trên StackOverflow để bắt đầu!) - John Feminella
"Một sai lầm xảy ra tại văn phòng, và mọi mục nhập trong mỗi cuốn sách điện thoại có thêm" 0 "ở cuối số điện thoại. Hãy lấy một số màu trắng ra và loại bỏ từng số không." <- đây không phải là thứ tự N bình phương. N được định nghĩa là kích thước của đầu vào. Kích thước của đầu vào là số lượng số điện thoại, là số lượng trên mỗi cuốn sách nhân với số lượng sách. Đó vẫn là một hoạt động thời gian tuyến tính. - Billy ONeal
@Billy: Trong ví dụ này, N là số người trong một cuốn sách. Bởi vì mọi người trong danh bạ điện thoại cũng có bản sao của cuốn sách, có N  giống nhau sổ điện thoại, mỗi cuốn sách có N người trong đó, là O (N ^ 2). - John Feminella
Không phải là O (1) trường hợp tốt nhất, thay vì trường hợp xấu nhất vì nó được đánh dấu lạ là? - Svip
Nó đã cho tôi O (long⅝n! N-55/2) thời gian để tìm một định nghĩa O (log n) mà cuối cùng cũng có ý nghĩa. +1 - iAteABug_And_iLiked_it


Nhiều câu trả lời hay đã được đăng lên câu hỏi này, nhưng tôi tin rằng chúng ta thực sự đang thiếu một câu trả lời quan trọng - cụ thể là câu trả lời minh họa.

Có nghĩa là gì để nói rằng chiều cao của một cây nhị phân hoàn chỉnh là O (log n)?

Bản vẽ sau mô tả cây nhị phân. Lưu ý cách mỗi cấp có chứa gấp đôi số lượng nút so với cấp trên (do đó nhị phân):

Binary tree

Tìm kiếm nhị phân là một ví dụ với độ phức tạp O(log n). Giả sử rằng các nút ở cấp dưới cùng của cây trong hình 1 thể hiện các mục trong một số bộ sưu tập được sắp xếp. Tìm kiếm nhị phân là một thuật toán phân chia và conquer, và bản vẽ cho thấy cách chúng ta sẽ cần (tối đa) 4 so sánh để tìm bản ghi chúng ta đang tìm kiếm trong tập dữ liệu 16 mục này.

Giả sử chúng tôi đã thay vào đó một tập dữ liệu với 32 yếu tố. Tiếp tục vẽ ở trên để thấy rằng bây giờ chúng ta sẽ cần 5 so sánh để tìm thấy những gì chúng ta đang tìm kiếm, vì cây đã chỉ phát triển một cấp độ sâu hơn khi chúng ta nhân số lượng dữ liệu. Kết quả là, độ phức tạp của thuật toán có thể được mô tả như một thứ tự lôgarit.

Vẽ đồ thị log(n) trên một mảnh giấy trơn, sẽ dẫn đến biểu đồ nơi sự tăng của đường cong giảm tốc như n tăng:

O(log n)


510
2018-02-21 22:22



"Chú ý cách mỗi cấp có chứa số lượng nút gấp đôi so với mức trên (do đó nhị phân)" Điều này là không chính xác. Những gì bạn mô tả là cân bằng Cây nhị phân. Cây nhị phân chỉ có nghĩa là mỗi nút có tối đa hai con. - Oenotria
Trong thực tế, nó là một cây nhị phân cân bằng rất đặc biệt, được gọi là cây nhị phân hoàn chỉnh. Tôi đã chỉnh sửa câu trả lời nhưng cần ai đó phê duyệt câu trả lời. - user21820
Một cây nhị phân hoàn chỉnh không cần phải có mức cuối cùng để được lấp đầy hoàn toàn. Tôi sẽ nói, một 'cây nhị phân đầy đủ' là thích hợp hơn. - Mr. AJ
Câu trả lời của bạn cố gắng trả lời cụ thể hơn cho vấn đề ban đầu của OP, vì vậy nó tốt hơn câu trả lời được chấp nhận hiện tại (IMO), nhưng nó vẫn còn rất không đầy đủ: bạn chỉ đưa ra một ví dụ và 2 hình ảnh ... - nbro
Cây này có 31 mục trong đó, không phải 16. Tại sao nó được gọi là tập dữ liệu 16 mục? Mỗi nút trên nó đại diện cho một số, nếu không nó sẽ là một cây nhị phân không hiệu quả: P - Perry Monschau


O(log N) về cơ bản có nghĩa là thời gian đi lên tuyến tính trong khi n tăng lên theo cấp số nhân. Vì vậy, nếu nó mất 1 thứ hai để tính toán 10 các yếu tố, nó sẽ mất 2 giây để tính toán 100 yếu tố, 3 giây để tính toán 1000 các yếu tố, v.v.

Nó là O(log n) khi chúng tôi phân chia và chinh phục loại thuật toán, ví dụ: tìm kiếm nhị phân. Một ví dụ khác là sắp xếp nhanh nơi mỗi lần chúng ta chia mảng thành hai phần và mỗi lần lấy O(N) thời gian để tìm một yếu tố trục. Do đó nó N O(log N) 


464
2018-02-21 20:18



Ba dòng trí tuệ mà đánh bại tất cả các câu trả lời tiểu luận khác ... :) Chỉ trong trường hợp ai đó đang thiếu nó, trong bối cảnh lập trình, cơ sở của log là 2 (không phải 10), vì vậy O (log n) quy mô như 1 giây cho 10 các phần tử, 2 giây cho 20, 3 cho 40, v.v. - nawfal
Đồng ý, súc tích và rõ ràng, mặc dù câu hỏi kết thúc từ OP là làm thế nào để xác định một hàm logarit, chứ không phải là "nó là gì" - Adam
có, hàm logarit là nghịch đảo hàm mũ. ((log x) a) là nghịch đảo của (công suất x). Phân tích định tính các hàm này với đồ thị sẽ mang lại trực giác hơn. - overexchange
Điều này đã cho tôi khoảng 3 lần đọc để nhận ra nó không sai. Thời gian đi lên tuyến tính, trong khi số lượng các phần tử là mũ. Điều này có nghĩa là nhiều yếu tố hơn trong thời gian ít hơn. Đây là việc đánh thuế tinh thần cho những người hình dung lognhư đường cong nhật ký quen thuộc trên biểu đồ. - Qix
Tôi nghĩ rằng đây là một câu trả lời rất tốt, ngoại trừ phần mà nó tuyên bố rằng tìm kiếm nhị phân là một thuật toán phân chia và chinh phục. Nó không phải là. - code_dredd


Lời giải thích dưới đây là sử dụng hoàn toàn cân bằng cây nhị phân để giúp bạn hiểu cách chúng tôi nhận được sự phức tạp về thời gian logarit.

Cây nhị phân là một trường hợp có vấn đề về kích thước n được chia thành vấn đề phụ có kích thước n / 2 cho đến khi chúng tôi gặp vấn đề về kích thước 1:

height of a binary tree

Và đó là cách bạn nhận được O (log n) là số lượng công việc cần phải được thực hiện trên cây trên để đạt được một giải pháp.

Một thuật toán phổ biến với độ phức tạp thời gian O (log n) là Tìm kiếm nhị phân có quan hệ đệ quy là T (n / 2) + O (1) tức là ở mỗi cấp độ tiếp theo của cây bạn phân chia vấn đề thành một nửa và thực hiện công việc bổ sung liên tục.


198
2017-10-26 19:33



newbie ở đây. Vì vậy, bạn có thể nói chiều cao cây là tỷ lệ phân chia theo đệ quy để đạt được kích thước n = 1? - Cody


Nếu bạn có một chức năng cần:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Sau đó, nó cần đăng nhập2(n) thời gian. Các Ký hiệu Big O, nói một cách lỏng lẻo, có nghĩa là mối quan hệ chỉ cần đúng với n lớn, và các yếu tố không đổi và các thuật ngữ nhỏ hơn có thể bỏ qua.


121
2018-02-21 20:11



là log2 (n) giống như o (log n)? - Sven van den Boogaart
Có, xem bình luận của nawfal cho một câu trả lời ở đây: (copy-paste) - trong bối cảnh lập trình, cơ sở của log là 2 (không phải 10), vì vậy tỷ lệ O (log n) như 1 giây cho 10 phần tử, 2 giây cho 20 , 3 cho 40 v.v. - Andrejs


Tổng quan

Những người khác đã đưa ra ví dụ sơ đồ tốt, chẳng hạn như sơ đồ cây. Tôi không thấy bất kỳ ví dụ mã đơn giản nào. Vì vậy, ngoài lời giải thích của tôi, tôi sẽ cung cấp một số thuật toán với các câu lệnh in đơn giản để minh họa sự phức tạp của các loại thuật toán khác nhau.

Đầu tiên, bạn sẽ muốn có một ý tưởng chung về Logarithm, mà bạn có thể nhận được từ https://en.wikipedia.org/wiki/Logarithm . Sử dụng khoa học tự nhiên e và nhật ký tự nhiên. Các môn đệ kỹ thuật sẽ sử dụng log_10 (log base 10) và các nhà khoa học máy tính sẽ sử dụng log_2 (log base 2) rất nhiều, vì các máy tính dựa trên nhị phân. Đôi khi bạn sẽ thấy các từ viết tắt của nhật ký tự nhiên ln(), các kỹ sư thường rời khỏi _10 và chỉ sử dụng log() và log_2 được viết tắt là lg(). Tất cả các loại logarit đều phát triển theo kiểu tương tự, đó là lý do chúng chia sẻ cùng một loại log(n).

Khi bạn nhìn vào các ví dụ mã dưới đây, tôi khuyên bạn nên xem xét O (1), sau đó là O (n), sau đó là O (n ^ 2). Sau khi bạn tốt với những người, sau đó nhìn vào những người khác. Tôi đã bao gồm các ví dụ rõ ràng cũng như các biến thể để chứng minh những thay đổi tinh tế vẫn có thể dẫn đến cùng một phân loại như thế nào.

Bạn có thể nghĩ về O (1), O (n), O (logn), vv như là các lớp hoặc danh mục tăng trưởng. Một số loại sẽ mất nhiều thời gian hơn so với những loại khác. Các danh mục này giúp chúng tôi có cách đặt hàng hiệu suất thuật toán. Một số phát triển nhanh hơn khi n đầu vào tăng lên. Bảng dưới đây cho thấy tăng trưởng số lượng. Trong bảng dưới đây nghĩ về log (n) là trần của log_2.

enter image description here

Các ví dụ mã đơn giản của nhiều danh mục O lớn:

O (1) - Ví dụ về thời gian không đổi:

  • Thuật toán 1:

Thuật toán 1 in hello một lần và nó không phụ thuộc vào n, do đó, nó sẽ luôn luôn chạy trong thời gian không đổi, vì vậy nó là O(1).

print "hello";
  • Thuật toán 2:

Thuật toán 2 in hello 3 lần, tuy nhiên nó không phụ thuộc vào kích thước đầu vào. Ngay cả khi n phát triển, thuật toán này sẽ luôn chỉ in hello 3 lần. Điều đó được nói 3, là một hằng số, vì vậy thuật toán này cũng O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Ví dụ về lôgarit:

  • Thuật toán 3 - Hành động này giống như "log_2"

Thuật toán 3 thể hiện thuật toán chạy trong log_2 (n). Lưu ý hoạt động của vòng lặp for bội số giá trị hiện tại của i bằng 2, vì vậy i đi từ 1 đến 2 đến 4 đến 8 đến 16 đến 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Thuật toán 4 - Hành động này giống như "log_3"

Thuật toán 4 thể hiện log_3. Để ý i đi từ 1 đến 3 đến 9 đến 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Thuật toán 5 - Hành vi này giống như "log_1.02"

Thuật toán 5 là quan trọng, vì nó giúp cho thấy rằng miễn là số lớn hơn 1 và kết quả được lặp đi lặp lại nhân với chính nó, rằng bạn đang xem xét một thuật toán logarit.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - Ví dụ về thời gian tuyến tính:

  • Thuật toán 6

Thuật toán này rất đơn giản, in số lần chào n lần.

for(int i = 0; i < n; i++)
  print "hello";
  • Thuật toán 7

Thuật toán này cho thấy một biến thể, nơi nó sẽ in hello n / 2 lần. n / 2 = 1/2 * n. Chúng ta bỏ qua hằng số 1/2 và thấy rằng thuật toán này là O (n).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Ví dụ:

  • Thuật toán 8

Hãy nghĩ về điều này như một sự kết hợp của O(log(n)) và O(n). Làm tổ cho các vòng giúp chúng ta có được O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Thuật toán 9

Thuật toán 9 giống như thuật toán 8, nhưng mỗi vòng lặp đã cho phép các biến thể, mà vẫn dẫn đến kết quả cuối cùng là O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n bình phương Ví dụ:

  • Thuật toán 10

O(n^2) thu được một cách dễ dàng bằng cách làm tổ chuẩn cho các vòng lặp.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Thuật toán 11

Giống như thuật toán 10, nhưng với một số biến thể.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n cubed Ví dụ:

  • Thuật toán 12

Điều này giống như thuật toán 10, nhưng với 3 vòng thay vì 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Thuật toán 13

Giống như thuật toán 12, nhưng với một số biến thể vẫn mang lại O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Tóm lược

Ở trên đưa ra một số ví dụ thẳng về phía trước và các biến thể để giúp chứng minh những thay đổi tinh tế nào có thể được giới thiệu thực sự không thay đổi phân tích. Hy vọng nó cung cấp cho bạn thông tin chi tiết đầy đủ.


108
2018-04-26 22:50



Tuyệt vời. Lời giải thích tốt nhất cho tôi mà tôi từng thấy. Nó sẽ đẹp hơn nếu O(n^2) được ghi nhận là sự kết hợp của O(n) và O(n), vì thế O(n) * O(n) = O(n * n) = O(n^2). Nó cảm thấy như một chút nhảy mà không có phương trình này. Đây là sự lặp lại lời giải thích trước, nhưng tôi nghĩ sự lặp lại này có thể cung cấp thêm sự tự tin cho độc giả để hiểu. - Eonil
@james cảm ơn câu trả lời tuyệt vời - Asthme
Đây chỉ đơn giản là giải thích tốt nhất từ ​​trước tới giờ. - Edgar Kiljak


Thời gian chạy logarit (O(log n)) về cơ bản có nghĩa là thời gian chạy tăng theo tỷ lệ với logarit kích thước đầu vào - làm ví dụ, nếu 10 mục mất nhiều thời gian nhất định xvà 100 mặt hàng mất nhiều nhất, giả sử, 2xvà 10.000 mục mất nhiều nhất 4x, sau đó nó trông giống như một O(log n) thời gian phức tạp.


84
2018-02-21 20:10



log2 hoặc log10 không liên quan. Chúng chỉ khác nhau theo một yếu tố tỷ lệ, mà làm cho chúng theo cùng thứ tự, tức là chúng vẫn tăng trưởng với cùng tốc độ. - Noldorin
Điều thú vị về logarit là khi so sánh chiều cao tương đối, cơ sở chính xác bạn sử dụng không quan trọng. log 10,000 / log 100 là 2 bất kể bạn sử dụng nền tảng nào. - Anon.
Để được nitpicky, O (lg n) có nghĩa là thời gian chạy là nhất tỷ lệ thuận với lg n. Những gì bạn mô tả là Theta (lg n).
@rgrig: Đó là sự thật. Tôi đã chỉnh sửa trong một vài "tối đa" để chỉ ra bản chất giới hạn trên của big-O. - Anon.
@rgrig ông mô tả cả O và theta: Theta (lg n) ngụ ý O (lg n) - klochner


Lôgarit

Ok, hãy thử và hiểu đầy đủ về logarit thực sự là gì.

Hãy tưởng tượng chúng tôi có một sợi dây thừng và chúng tôi đã gắn nó với một con ngựa. Nếu sợi dây thừng được gắn trực tiếp với con ngựa, thì con ngựa cần phải rút đi (nói, từ một người) là trực tiếp 1.

Bây giờ hãy tưởng tượng sợi dây được vòng quanh một cái cột. Con ngựa để lấy đi bây giờ sẽ phải kéo nhiều lần khó hơn. Lượng thời gian sẽ phụ thuộc vào độ nhám của sợi dây và kích thước của cột, nhưng giả sử nó sẽ nhân lên sức mạnh của một người bằng 10 (khi sợi dây tạo ra một vòng quay hoàn chỉnh).

Bây giờ nếu dây được lặp lại một lần, con ngựa sẽ cần phải kéo gấp 10 lần. Nếu con người quyết định làm cho nó thực sự khó khăn cho con ngựa, ông có thể lặp lại sợi dây thừng một lần nữa quanh một cực, tăng sức mạnh của nó thêm 10 lần. Vòng thứ ba sẽ tăng thêm sức mạnh thêm 10 lần nữa.

enter image description here

Chúng ta có thể thấy rằng đối với mỗi vòng lặp, giá trị tăng thêm 10. Số lượt cần để nhận được bất kỳ số nào được gọi là logarit của số đó, nghĩa là chúng ta cần 3 bài viết để tăng sức mạnh lên 1000 lần, 6 bài viết để nhân sức mạnh của bạn 1.000.000.

3 là lôgarit của 1.000, và 6 là lôgarit của 1.000.000 (cơ số 10).

Vậy O (log n) thực sự có ý nghĩa gì? 

Trong ví dụ trên, 'tốc độ tăng trưởng' của chúng tôi là O (log n). Đối với mỗi vòng lặp bổ sung, lực dây của chúng tôi có thể xử lý gấp 10 lần:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Bây giờ ví dụ trên đã sử dụng cơ sở 10, nhưng may mắn thay cơ sở của nhật ký là không đáng kể khi chúng ta nói về ký hiệu o lớn.

Bây giờ hãy tưởng tượng bạn đang cố gắng đoán một số từ 1-100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Bây giờ nó đã cho bạn 7 đoán để có được quyền này. Nhưng mối quan hệ ở đây là gì? Số lượng vật phẩm nhất mà bạn có thể đoán được từ mỗi lần đoán thêm là bao nhiêu?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Sử dụng biểu đồ, chúng ta có thể thấy rằng nếu chúng ta sử dụng một tìm kiếm nhị phân để đoán một số từ 1-100 nó sẽ đưa chúng ta nhất 7 lần thử. Nếu chúng tôi có 128 con số, chúng tôi cũng có thể đoán số trong 7 trang nhưng 129 số sẽ đưa chúng tôi nhất 8 cố gắng (trong quan hệ với logarit, ở đây chúng ta sẽ cần 7 dự đoán cho một phạm vi giá trị 128, 10 dự đoán cho một phạm vi giá trị 1024. 7 là logarit của 128, 10 là logarit của 1024 (base 2)).

Lưu ý rằng tôi đã in đậm 'nhiều nhất'. Ký hiệu o lớn luôn đề cập đến trường hợp xấu hơn. Nếu bạn may mắn, bạn có thể đoán số trong một lần thử và vì vậy trường hợp tốt nhất là O (1), nhưng đó là một câu chuyện khác.

Chúng ta có thể thấy rằng đối với mỗi dự đoán, tập dữ liệu của chúng tôi đang thu hẹp lại. Một quy tắc hay để xác định xem thuật toán có thời gian logarit không   để xem liệu tập dữ liệu có co lại theo một thứ tự nhất định sau mỗi lần lặp hay không

Điều gì về O (n log n)?

Bạn cuối cùng sẽ đi qua một thời gian linerarithmic O (n log (n) thuật toán. Quy tắc của ngón tay cái ở trên áp dụng một lần nữa, nhưng lần này hàm logarit phải chạy n lần, ví dụ: giảm kích thước của một danh sách n lần, xảy ra trong các thuật toán như một mergesort.

Bạn có thể dễ dàng xác định nếu thời gian thuật toán là n log n. Tìm một vòng lặp ngoài lặp qua danh sách (O (n)). Sau đó xem xét xem có vòng lặp bên trong hay không. Nếu vòng lặp bên trong là cắt / giảm tập dữ liệu trên mỗi lần lặp, vòng lặp đó là (O (log n), và vì vậy thuật toán tổng thể là = O (n log n).

Tuyên bố từ chối trách nhiệm: Ví dụ về dây-lô-gô được lấy từ sự xuất sắc Cuốn sách Delight của nhà toán học của W.Sawyer. 


55
2017-10-08 14:27





Bạn có thể nghĩ về O (log N) bằng trực giác bằng cách nói rằng thời gian tỷ lệ thuận với số chữ số trong N.

Nếu một phép toán thực hiện thời gian không đổi làm việc trên mỗi chữ số hoặc bit của đầu vào, toàn bộ thao tác sẽ mất thời gian tỉ lệ với số chữ số hoặc bit trong đầu vào, không phải độ lớn của đầu vào; do đó, O (log N) thay vì O (N).

Nếu một phép toán thực hiện một loạt các quyết định thời gian liên tục, mỗi nửa sẽ giảm (giảm 3, 4, 5 ..) kích thước của đầu vào cần xem xét, toàn bộ sẽ mất thời gian tỉ lệ với log 2 (base 3) , base 4, base 5 ...) của kích thước N của đầu vào, chứ không phải là O (N).

Và cứ thế.


54
2018-02-21 20:13



Đủ chính xác và dễ nắm bắt hơn hầu hết các giải thích, tôi nghĩ. - T .
đó là một lời giải thích của log<sub>10</sub> N, Là nó? - LiuYan 刘研
@LiuYan 刘 研 họ không nói số cơ sở là số chữ số. Trong mọi trường hợp, log₂ (n) = log₁₀ (n) / log₁₀ (2) và 1 / log₁₀ (2) là một hệ số không đổi, với cùng một nguyên tắc áp dụng cho tất cả các căn cứ khác. Điều này cho thấy hai điều. Thứ nhất, nguyên tắc của moonshadow áp dụng cho bất kỳ cơ sở nào (mặc dù đáy thấp hơn, ít "jags" trong ước tính) và O (log n) là O (log n) cho dù kết quả tính toán đã dẫn bạn đến kết luận đó . - Jon Hanna


Cách tốt nhất tôi luôn luôn phải hình dung về mặt tinh thần một thuật toán chạy trong O (log n) như sau:

Nếu bạn tăng kích thước bài toán theo số lượng nhân (nghĩa là nhân kích thước của nó với 10), công việc chỉ được tăng thêm một số phụ gia.

Áp dụng điều này cho câu hỏi cây nhị phân của bạn để bạn có một ứng dụng tốt: nếu bạn tăng gấp đôi số lượng nút trong cây nhị phân, chiều cao chỉ tăng 1 (một số phụ gia). Nếu bạn tăng gấp đôi nó một lần nữa, nó vẫn chỉ tăng lên 1. (Rõ ràng là tôi giả định nó vẫn cân bằng và như vậy). Bằng cách đó, thay vì tăng gấp đôi công việc của bạn khi kích thước vấn đề được nhân lên, bạn chỉ làm việc nhiều hơn một chút. Đó là lý do tại sao các thuật toán O (log n) là tuyệt vời.


48
2018-02-22 19:51





Nhật ký là gìb(n)?

Đó là số lần bạn có thể cắt nhật ký độ dài n thành nhiều phần bằng nhau trước khi đến một phần có kích thước 1.


33
2018-03-19 19:28



Nhận xét tuyệt vời! Nó ngắn gọn và chính xác là câu trả lời tôi đang làm. - DennisL
giải thích tốt - mAc