Thời gian chạy của các hàm toán học toán học

Question

Tôi có thể chuyển thông tin về thời gian tính toán của các hàm toán học ở đâu? Có bất kỳ nghiên cứu (tổng quát) nào với bất kỳ số lượng nghiêm ngặt nào đã được thực hiện?

Ví dụ, thời gian tính toán của

liên tục + thường xuyên

thông thường phải mất O (1).

Giả sử tôi muốn bắt đầu sử dụng toán học như tích phân và tôi muốn nhận được một xấp xỉ tiệm cận với các tích phân khác nhau. Đã có một nghiên cứu tiêu chuẩn về điều này, hoặc tôi phải lấy những thông tin tôi có và tìm ra xấp xỉ của riêng tôi. Tôi rất quan tâm đến cách tiếp cận tiêu chuẩn này và tôi muốn biết liệu nó có tồn tại hay không.

Đây là động lực của tôi: Tôi đang ở giữa viết một bài báo chỉ ra sự tương đương giữa các vấn đề về NP khó và một số phương trình toán học nhất định. Dường như có thể sử dụng cho một nghiên cứu về thời gian tính toán toán học được tổng quát hóa như một khoa học mới.

EDIT: Tôi đoán tôi đang tự hỏi liệu có một độ phức tạp tính toán tiêu chuẩn cho bất kỳ toán học nào không thể tránh được. Tôi tự hỏi nếu có ai đã nghiên cứu câu hỏi này. Tôi rất muốn xem những gì người khác đã thử.

CHỈNH SỬA 2: Danh sách Wikipedia "Lý thuyết phức tạp tính toán" trong bách khoa toàn thư của họ, mà tôi nghĩ có thể phù hợp với hóa đơn. Tôi vẫn tự hỏi liệu một người nào đó đã nghiên cứu điều này có thể khẳng định điều này không.

Answer 1

Không có bộ sưu tập công việc được thu thập, nhưng hoạt động trên các hàm gần đúng sẽ đến gần. Ví dụ, bạn muốn biết rằng xấp xỉ sin (x) trong một lỗi epsilon có thể được thực hiện theo thời gian tỉ lệ với một số đa thức trong log (x) và 1/epsilon. Không có một lý thuyết chung ở đây (bạn nên tìm kiếm thông tin phức tạp mặc dù), và tập trung vào các chức năng cụ thể có thể giúp đỡ.

Answer 2

Toán học "Chuẩn" không có khái niệm phức tạp về thuật toán. Đó là dành riêng cho các thuật toán máy tính.

Có nhiều cách để phân tích hành vi động của các giải pháp của phương trình. Những thứ như sự hội tụ quan trọng đối với các nhà toán học.

Bạn có thể hỏi độ phức tạp của thuật toán tích hợp euler so với Runge-Kutta bậc 5 để tích hợp. Họ sẽ so sánh dựa trên số lượng các đánh giá chức năng cần thiết và ổn định bước thời gian.

Nhưng "thời gian chạy" của giải pháp cho Định lý cuối cùng của Fermat là gì? Còn vấn đề thách thức cuối cùng của David Hilbert thì sao? Là "thời gian chạy" cho một thế kỷ và đếm? Thời gian chạy của bạn để giải quyết một phương trình vi phân một phần bằng cách sử dụng tách biến là gì?

Khi bạn nghĩ về nó theo cách đó, bạn có hiểu rõ hơn về lý do mọi người sẽ bị loại bỏ bởi câu hỏi của bạn không?

Answer 3

Có, đối với các hàm toán học khác nhau, độ phức tạp tính toán (thời gian chạy) của tính toán hàm đã được nghiên cứu. Điều này có thể khác nhau tùy thuộc vào mô hình tính toán. Ví dụ: thêm hai số n bit có thời gian Θ (n), nhân chúng mất thời gian Θ (n log n) (sử dụng FFT), việc tìm kiếm gcd của chúng mất khoảng thời gian Θ (n) với thông thường Thuật toán Euclide và Θ (n (log n) (nhật ký log n)) với thuật toán tốt hơn, v.v. Đối với các công cụ phức tạp hơn như tích phân, rõ ràng nó phụ thuộc vào thuật toán bạn sử dụng.

Answer 4

user389117,

Tôi nghĩ rằng tiềm thức bạn muốn suy ra sự phức tạp của tính toán một loại toán học từ các hình thức của loại toán học này.

Ví dụ: Một loại toán học liên quan đến bình phương của biến (x^2) bạn nghĩ (ít nhất là tiềm thức) rằng độ phức tạp của tính toán là anologous với x^2 nên độ phức tạp nên giống như O (n^2) hoặc có một quy trình chuẩn để suy ra hình thức phức tạp từ dạng của phương trình toán học.

Cả hai đều có những phẩm chất khác nhau và không thể suy ra chất lượng này từ chất lượng khác.

Tôi sẽ cung cấp cho bạn một ví dụ: Trong tất cả các thuật toán được viết bằng mã giả và sau đó các nhà khoa học suy ra sự phức tạp của mã giả.

Mã giả phải chắc chắn được viết và sau đó bạn tính toán độ phức tạp.

Không có cách kỳ diệu nào để có được sự phức tạp xuất phát từ hình thức của thứ bạn muốn tính toán.

Ngay cả khi bạn tính toán độ phức tạp và bạn thấy biểu mẫu tương tự với dạng phương trình được tính thì tôi nghĩ nó khó, ít nhất là ở vị trí đầu tiên, để bạn chuyển đổi nhận xét đó từ giả khoa học sang khoa học.

Chúc may mắn!