Độ phức tạp của bài toán dò khóa (Brute-Force) được xác định như thế nào?

#1

Cho mọi người.
Cho mình hỏi, độ phức tạp của bài toán dò khóa được tính dựa theo cách nào sau đây:

  1. Số phép thử tối đa cần phải thử đề tìm ra khoá.
  2. Số phép thử trung bình để tìm ra khóa.

Chú thích: bài toán dò khóa (Brute-Force) là thuật ngữ dùng trong kĩ thuật mật mã, dùng để chỉ kiểu tấn công bằng cách thử từng khóa một cho đến khi phù hợp. Cụ thể, nến khóa có chiều dài n bit thì số phép thử tối đa là 2^n , và số phép thử trung bình là bằng phân nửa số phép thử tối đa, tức là 2^(n-1)

Cảm ơn mọi người. :smile:

#2

Cả hai cái đó đều được dùng để đánh giá độ phức tạp, một cái là worst-case complexity một cái là average-case complexity. Thông thường về mặt lý thuyết, người ta quan tâm tới worst-case nhiều hơn, một phần vì nó đơn giản để đánh giá hơn và nó là giới hạn trên của thuật toán. Average case không phải thuật toán nào cũng tìm được.
Trong trường hợp của bạn thì cả worst và average đều có độ phức tạp O(2^n), do đó phân ra cũng không có khác biệt.

#3

Khác nhau nha anh @Itachi_Citus .

#4

Nó là như nhau khi đánh giá độ phức tạp thuật toán. 2^(n-1) = 1/2 * (2^n). 1/2 là hằng số, trong đánh giá độ phức tạp, để đơn giản ta có thể bỏ các hằng số này đi (Về mặt lý thuyết thì không phải là bỏ, mà nó là tương đương nếu bạn đọc định nghĩa về Big-O). Do đó cả hai trường hợp độ phức tạp là O(2^n).

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?