Độ phức tạp của thuật toán: Cách xem "tiêu thụ điện năng" làm tham số?

Question

Không gian và thời gian được coi là phong vũ biểu phân tích độ phức tạp của thuật toán. Nhưng những ngày này với sự hiện diện của GPU trên thiết bị di động, có rất nhiều ứng dụng có thể sử dụng hiệu năng cao đó để chạy các thuật toán phức tạp trên thiết bị di động. Ví dụ: khuôn khổ Kim loại của iOS có thể được sử dụng cho các hoạt động GPGPU. Nhưng không cần phải nói nó tiêu thụ rất nhiều năng lượng. Vì vậy, câu hỏi của tôi là, nếu tôi đang phát triển/thực hiện, một thuật toán tìm kiếm đồ thị, trên thiết bị di động, tôi cũng không nên xem xét độ phức tạp "sức mạnh" của thuật toán cùng với không gian thời gian? Bây giờ, tôi biết các đối số có thể là sức mạnh là một cái gì đó mà các thuật toán không tiêu thụ chính nó trực tiếp và tôi hoàn toàn đồng ý với điều đó. Vì vậy, có lẽ ngữ pháp của tôi ở đây là không chính xác khi nói rằng sức mạnh là một chiều hướng khác để đo lường hiệu quả của thuật toán. Nhưng không nên được coi là một thước đo hiệu suất của một thuật toán?

Answer 1

Để thực hiện điều này, bạn cần một mô hình tiêu thụ năng lượng mà bạn có thể liên quan đến các hoạt động nguyên tử trong thuật toán của mình.

Giống như "một nhân tiêu thụ một đơn vị năng lượng" và "khe cắm bộ nhớ sử dụng hai đơn vị năng lượng trên một đơn vị thời gian". Có lẽ mối quan hệ Energy = Time x Space có thể có ý nghĩa.

Dù sao, mô hình "ngây thơ" này có thể bị hiện tượng tương tự như mô hình phức tạp thời gian: nó không có bất kỳ sự tương đồng nào với hành vi của kiến ​​trúc hiện đại và có thể sai theo thứ tự độ lớn.

Sử dụng các mô hình chính xác hơn sẽ chỉ khó phân tích.

Answer 2

No. Độ phức tạp giải thích cách thuật toán quy mô theo thời gian/bộ nhớ. Sức mạnh sẽ là một chức năng của thời gian và bộ nhớ.

Giả sử bạn có thuật toán A - O (N^2) và B - O (N^3) và cả hai đều giải quyết cùng một vấn đề. Đối với n = 1000 B sử dụng 1 đơn vị quyền lực trong khi A sử dụng 20. Bây giờ khi bạn quy mô nó lên đến n = 10k B sẽ cần 1000 đơn vị quyền lực trong khi A sẽ chỉ cần 2000. Tại n = 100k B sẽ cần 1'000 ' 000 trong khi A sẽ cần 200'000. Và cứ thế. Điều này giả định rằng mức tiêu thụ năng lượng là hằng số để thực hiện thuật toán.

Bằng cách này, điều tương tự cũng xảy ra theo thời gian. Ví dụ cho mảng ngắn không có gì nhịp đập tìm kiếm tuyến tính.

Đối với trường hợp cụ thể (hiển thị giao diện người dùng ở độ phân giải cố định), bạn nên đo mức sử dụng năng lượng và tối ưu hóa nó. Nhưng những gì làm việc cho giải pháp ngày hôm nay sẽ không nhất thiết phải là điều đúng ngày mai.