Không gian O (1) có nghĩa là gì? Tôi hiểu rằng các bước O (n) giống như thứ tự độ lớn của các phép tính mà thuật toán/chương trình tạo ra, nhưng không biết không gian O (n) là gì.Điều này có nghĩa là: các bước O (n) và không gian O (1)?
O (1) không gian nghĩa là bộ nhớ theo yêu cầu của thuật toán là hằng số, tức là không phụ thuộc vào kích thước của đầu vào.
O (n) không gian có nghĩa là bộ nhớ theo yêu cầu của thuật toán có (trong trường hợp xấu nhất) có cùng thứ tự độ lớn như kích thước của đầu vào.
Sửa: Thêm hai ví dụ:
Về cơ bản "O (n) bước và O (1) không gian" có nghĩa là số bước thực hiện quy mô tuyến tính (O (n)) với số lượng mục, nhưng số lượng bộ nhớ mất là hằng số.
vì vậy về cơ bản một cuộc gọi đệ quy thường sẽ là không gian O (n) và một quá trình lặp lại sẽ là O (1) vì bạn không chờ đợi (các) cuộc gọi đệ quy để kết thúc? – Devoted
Đã thêm hai ví dụ phổ biến. Vâng, bạn không thể thực sự tìm thấy các quy tắc chung về phức tạp thuật toán đệ quy và lặp đi lặp lại (nhưng nó có thể khó - không phải không thể - cho một thuật toán đệ quy có O (1) phức tạp không gian). – 3lectrologos
nếu cuộc gọi đệ quy của bạn sử dụng các biến mới mỗi khi được gọi thì có, nó sẽ là không gian O (n). Nếu quá trình lặp của bạn khởi tạo các biến mới trong một vòng lặp mà không giải phóng thì nó cũng sẽ là O (n). Tất cả phụ thuộc vào cách bạn thiết kế và mã hóa thuật toán. – Nikhil