Tôi bắt đầu học về sự phức tạp về thời gian và tôi đã xem các ví dụ về độ phức tạp thời gian cho một số loại đơn giản.Độ phức tạp về thời gian của thuật toán đồ thị độ sâu đầu tiên
Tôi muốn biết làm cách nào để tính toán độ phức tạp thời gian trung bình cho tìm kiếm theo chiều sâu trong biểu đồ với |V|=n và |E|=m, cho nút bắt đầu là 'u' và nút kết thúc là 'v'.
Độ phức tạp thời gian cho DFS là O (n + m). Chúng tôi nhận được sự phức tạp này xem xét thực tế là chúng tôi đang truy cập mỗi nút chỉ một lần và trong trường hợp của một cây (không có chu kỳ), chúng tôi đang vượt qua tất cả các cạnh một lần.
Ví dụ: nếu nút bắt đầu là u và nút kết thúc là v, chúng tôi đang nghĩ đến trường hợp xấu nhất khi v sẽ là nút được truy cập cuối cùng. Vì vậy, chúng tôi đang bắt đầu truy cập từng thành phần đầu tiên của thành phần được kết nối với u, sau đó là thành phần được kết nối của hàng xóm thứ hai, v.v .. cho đến khi thành phần được kết nối của hàng xóm gần nhất, nơi chúng tôi tìm thấy v. vượt qua cùng một cạnh nhiều lần.
kính trọng sir, Tôi mới đến phân tích phức tạp, thực sự tôi đang làm một dự án trên hệ điều hành, tôi đang cố gắng tìm các chu kỳ trong đồ thị phân bổ tài nguyên ... tôi tìm chu kỳ bằng cách sử dụng một sửa đổi chiều sâu tìm kiếm đầu tiên .. tôi đang cố gắng để so sánh sự phức tạp của thuật toán này với thuật toán của ngân hàng .. bạn có thể cung cấp cho derivation toán học của "hiệu suất trường hợp avergae" – Learner
"Hiệu suất trường hợp trung bình" là giá trị dự kiến (đó là một thuật ngữ từ lý thuyết xác suất) của thời gian chạy trên một số phân bố xác suất giả định đầu vào. –
nó sẽ là O (n + m) nếu biểu đồ được đưa ra dưới dạng danh sách kề nhưng nếu biểu đồ ở dạng ma trận kề thì độ phức tạp là O (n * n), phải đi qua toàn bộ hàng cho đến khi chúng ta tìm thấy một cạnh.
Tôi biết điều này là quá muộn .. Nhưng đối với những người khác có thể tìm kiếm, đây là một phân tích chi tiết. http://techieme.in/depth-first-traversal – dharam