Độ phức tạp Big-O của mã của tôi là gì?

Question

Cho một mảng các số nguyên, viết một phương thức trả về cặp bài độc đáo để tăng thêm dữ liệu 100.

Ví dụ:

sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51] 
sample_output = [[1,99], [0,100], [10,90], [51,49], [50,50]] 

Tôi đã giải quyết vấn đề này vào cuối tuần này và trong khi giải pháp của tôi dường như khả năng mở rộng và hiệu quả, tôi muốn xác định độ phức tạp thời gian tồi tệ nhất của giải pháp của tôi là gì?

Đây là giải pháp của tôi:

def solution(arr) 
    res = [] 
    h = Hash.new 

    # this seems to be O(N) 
    arr.each do |elem| 
    h[elem] = true 
    end 

    # how do I determine what Time complexity of this could be? 
    arr.each do |elem| 
    if h[100-elem] 
     h[100-elem] = false 
     h[elem] = false 
     res << [elem, 100-elem] 
    end 
    end 
    res 
end 

Nếu cả hai vòng là O (N) mỗi, và tôi thêm chúng lên: O (N + N), điều này sẽ bằng O (2N) và lấy 2 để được một hằng số, tôi có thể giả định giải pháp của tôi là O (N)?

Answer 1

Bạn là chính xác. Big-O của mã này sẽ là O(n) nếu bạn xem xét thời gian chạy được tính khấu hao của tìm kiếm/chèn băm.

Nếu bạn thực hiện trường hợp tìm kiếm/chèn băm đúng nhất (O(n)), thì đó sẽ là O(n^2).

See Wikipedia on Hash Tables

Answer 2

Câu hỏi đặt ra có thể được hỏi về mức độ phức tạp thời gian của băm, nhưng đối với các vấn đề cụ thể, băm mà sẽ thực hiện tốt hơn như là một mảng của bools lập chỉ mục của 0..sum đầu vào (100 trong trường hợp này). Điều đó sẽ có thời gian liên tục tốt nhất, tồi tệ nhất và trung bình.

Cách tiếp cận đó đơn giản hơn để tính toán độ phức tạp của O (N).