2010-07-05 10 views
5

Ký hiệu O lớn chính xác cho thuật toán chạy trong thời gian triangular là gì? Dưới đây là ví dụ:Ký hiệu Big O cho số tam giác?

func(x): 
    for i in 0..x 
    for j in 0..i 
     do_something(i, j) 

Bản năng đầu tiên của tôi là O(n²), nhưng tôi không hoàn toàn chắc chắn.

+1

Bạn đúng ... O ((n + 1) chọn 2) = O (n^2) theo định nghĩa. – Protostome

Trả lời

12

Có, N * (N + 1)/2, khi bạn thả các hằng số và các thuật ngữ bậc thấp hơn, khiến bạn có N-bình phương.

1

Vâng, O(n^2) chắc chắn là chính xác. Nếu tôi nhớ chính xác, O luôn là giới hạn trên, vì vậy, O(n^3) cũng phải là IMO, cũng như O(n^n) hoặc bất kỳ thứ gì. Tuy nhiên O(n^2) dường như là một trong những chặt chẽ nhất có thể dễ dàng khấu trừ.

0

Nếu bạn nghĩ về mặt toán học, diện tích của tam giác bạn đang tính là ((n+1)^2)/2. Do đó, thời gian tính toán: O ((((+ 1)^2)/2)

0

Thời gian tính toán tăng theo hệ số N * (N + 1)/2 cho mã này. Đây là bản chất O (N^2).

0

khi tăng đầu vào từ N đến 2n sau đó thời gian chạy của thuật toán của bạn sẽ tăng từ t đến 4t

do đó thời gian chạy là tỷ lệ thuận với bình phương của kích thước đầu vào

nên thuật toán là O (n^2)

-1

O (! n) xử lý các trường hợp để tính toán giai thừa (thời gian tam giác).

Nó cũng có thể được biểu diễn dưới dạng O (n^2) đối với tôi điều này có vẻ hơi sai lệch vì số tiền được thực hiện luôn bằng một nửa so với O (n^2) sẽ thực hiện.

+0

Theo định nghĩa, 'O (0,5 * n^2) == O (n^2)' (một sự bình đẳng nắm giữ cho bất kỳ hệ số không khác không, trên thực tế), do đó, từ một quan điểm lý thuyết nghiêm ngặt, điều này không gây hiểu nhầm. :-) – Gijs

+1

-1. [Factorial] (http://en.wikipedia.org/wiki/Factorial) không giống với [số tam giác] (http://en.wikipedia.org/wiki/Triangular_number). – gilly3