Xét máy Turing nhận đầu vào 1^n (chuỗi n dấu 1). Máy quét phải qua toàn bộ n dấu 1 (mất n bước để tới ô trắng), rồi quay đầu quét trái trở về ô trái nhất (mất thêm n bước), cuối cùng thực hiện 1 bước dừng khi ra khỏi vùng dữ liệu.
Số bước là hàm của độ dài đầu vào: T(n) = 2n + 1. Đây là ví dụ độ phức tạp thời gian tuyến tính O(n).
Cho n, hãy in ra T(n).
Ví dụ: n = 3 → T(3) = 2·3 + 1 = 7.
Một số nguyên n.
0 ≤ n ≤ 1000000000.
Một số nguyên: T(n) = 2n + 1.
Ví dụ:
Đầu vào:
3
Đầu ra:
7
Giải thích:
Đang tải editor...