Như đã đề cập trong câu hỏi, cần phải tìm tổng số (i, j) cặp trong mảng màtìm tổng số (i, j) cặp trong mảng như vậy mà tôi <j and a[i]> a [j]
(1) **i<j**
(2) **a[i]>a[j]**
trong đó i và j là chỉ số của mảng. Không có ràng buộc về không gian.
Câu hỏi của tôi là
1) Is there any approach which takes less than O(N^2) time?
2) if so what is least complexity ?
3) How do we prove that ?
Tôi hy vọng tôi rõ ràng với câu hỏi này.
Cách tiếp cận của tôi là như sau
Một cách để thực hiện câu hỏi là sử dụng dấu vân tay mất thời gian O (N^2).
Nhưng tôi nghĩ rằng có phải là một giải pháp tối ưu hóa tốt hơn cho câu hỏi này ở-nhất O (NlogN) sollution .Công lý do trực giác của tôi là như sau
Trực giác 1) For sorting an array in ascending order conditions we have are : for i<j , a[i]<a[j] which is similar to my question . I also read that sorting has lower bound of Omega(n log n) . So my question should also have Omega(n log n) . I may be completely wrong if so please correct me .
trực giác thứ hai của tôi là :
Giả sử chúng ta có một loạt các yếu tố như sau: 4,9,7,3,2,1,8,12
chúng tôi tính toán trên điều kiện cho các phần tử i<j , a[i]>a[j] 4, như tôi = 0 điểm đến 4, các giá trị có thể cho j là 3,4,5, trừ [0]> a [3], [0]> a [4], a [0]> a [5], vì vậy tổng số của tôi không có (i, j) cặp bây giờ là 3. Lần sau khi tôi tăng i (chỉ mục) thành 1, giá trị khả năng của j là 2,3,4,5,6. Nhưng chúng ta nên sử dụng thực tế là khi i = 0 (khi [i] = 4), chúng tôi đã tính 3 phần tử nhỏ hơn [i = 0], lần lượt nhỏ hơn [i = 1], vì vậy tôi sẽ không Nếu chúng ta có thể loại bỏ những tính toán không cần thiết thì chúng ta có thể giảm độ phức tạp xuống một cái gì đó nhỏ hơn O (N^2) hoặc không có giải pháp nào nhỏ hơn O (N^2) tồn tại. Nhưng nếu giải pháp tồn tại thì làm thế nào để chúng tôi làm điều đó. Tôi đã thử làm đồ thị nhưng những nỗ lực của tôi là vô ích.
Tiếp cận 1) In-order to obtain O(nlogn) complexity I think we need to tweak around quick sort or merge sort to get solution but problem here is, if we sort the array we loose the actual positions of elements.
Tiếp cận 2)In-order to get solution in O(NlogN) time I think using tree we may get the optimised sollution . I didn't get any clue.
Tiếp cận 3) If there exists any O(N) time algorithm it should be with hashing . But in this case simple hashing doest work .
Vì vậy, xin vui lòng cho tôi biết đó là những trực giác hay cách tiếp cận trên là chính xác (Nếu đúng mà cách tiếp cận sẽ dẫn đến sollution tối ưu hóa và làm thế nào).
Bạn có nghĩa là "* nhỏ hơn O (N^2) *" không? Tôi hỏi bởi vì về mặt kỹ thuật, O (N * 2) giống như O (N), và nó không rõ ràng những gì bạn có nghĩa là "O (N2)". – RBarryYoung
vâng, tôi có nghĩa là O (N^2) – Imposter
Bạn đang cố gắng tìm số lượng các cặp như vậy hoặc liệt kê chúng? –