Square Root (Integer)

Q: Độ phức tạp thời gian của thuật toán tìm căn bậc hai bằng tìm kiếm nhị phân là bao nhiêu?

Thời gian O(log x) và bộ nhớ O(1) : mỗi bước giảm một nửa phạm vi, vì vậy x = 2^31 - 1 cần 31 bước. Đếm tăng dần từ 0 cần O(√x) bước, tức là 46340 bước với cùng giá trị x .

Q: Phương pháp Newton tính căn bậc hai nguyên như thế nào?

Bắt đầu với r = x . Khi r × r > x , thay r bằng (r + x / r) / 2 bằng phép chia lấy phần nguyên. Mỗi bước đưa r giảm dần về phía căn bậc hai mà không vượt qua nó, và vòng lặp dừng tại phần nguyên của căn bậc hai. Với x = 2^31 - 1 , cần 19 bước.

DễTìm kiếm nhị phân Toán và mô phỏng

+10

Hàm của bạn nhận một số nguyên không âm x và trả về căn bậc hai nguyên của nó: số nguyên lớn nhất r sao cho r × r ≤ x. Nói cách khác, lấy phần nguyên của căn bậc hai, vì vậy nếu một số không phải là số chính phương thì kết quả là căn bậc hai của số chính phương nhỏ hơn liền kề. Hãy tự tính kết quả, không dùng hàm căn bậc hai hay hàm lũy thừa có sẵn.

Hàm

mySqrt(x: integer) → integer

xinteger: số nguyên không âm cần lấy căn bậc hai
Trả vềinteger: căn bậc hai của x được làm tròn xuống thành số nguyên

Ràng buộc

0 ≤ x ≤ 2³¹ - 1
Không gọi hàm căn bậc hai, hàm lũy thừa hoặc hàm số mũ có sẵn.

Ví dụ

Đầu vào: x = 17
Đầu ra: 4
Giải thích: 4 × 4 = 16 không vượt quá 17, nhưng 5 × 5 = 25 lớn hơn, nên căn bậc hai của 17 được làm tròn xuống 4.

Đầu vào: x = 49
Đầu ra: 7
Giải thích: 49 là một số chính phương, 7 × 7 = 49, nên không có gì bị làm tròn và đáp án chính xác là 7.

Câu hỏi mở rộng

Bạn sẽ tìm căn bậc ba nguyên như thế nào, tức số nguyên lớn nhất r thỏa mãn r × r × r ≤ x, nếu x cũng có thể âm?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Các số chính phương 0, 1, 4, 9, 16, v.v. được sắp xếp theo thứ tự, nên bạn có thể tìm kiếm nhị phân số cuối cùng có bình phương không lớn hơn x trong khoảng 31 bước. Vấn đề nằm ở tràn số: bình phương của một số ứng viên không phải lúc nào cũng vừa với 32 bit.

Đếm tăng dần từ số không

Ý tưởng

Bắt đầu từ r = 0 và tăng lên r + 1 khi bình phương số tiếp theo vẫn không lớn hơn x. Vòng lặp dừng ở giá trị r đầu tiên mà số kế tiếp quá lớn, đó chính là căn bậc hai. Với x = 17, các bình phương 1, 4, 9 và 16 đều phù hợp, còn 25 thì không, nên vòng lặp dừng ở 4.

Căn bậc hai lớn nhất ở đây là 46340, vì vậy vòng lặp chạy tối đa 46340 lần. Tuy nhiên, chi phí tăng theo đầu vào: một x 64 bit có thể cần khoảng 3 × 10^9 bước.

Thuật toán

Đặt root = 0.
Trong khi (root + 1) × (root + 1) ≤ x (với 64 bit), tăng root thêm 1.
Trả về root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Tìm kiếm nhị phân trên đáp án

Ý tưởng

Kiểm tra từng ứng viên từ 0 đến x xem bình phương của nó có nhỏ hơn hoặc bằng x không. Bình phương chỉ tăng, nên các câu trả lời là có cho đến căn bậc hai rồi chuyển thành không. Căn bậc hai là giá trị cuối cùng có câu trả lời là có. Tìm giá trị đó bằng tìm kiếm nhị phân, mỗi lần chia đôi phạm vi các ứng viên chưa được quyết định. Giữ giá trị có lớn nhất đã thấy đến thời điểm đó trong best.

Với x = 17, quá trình tìm kiếm kiểm tra 8 (64, quá lớn), 3 (9, vừa), 5 (25, quá lớn) và 4 (16, vừa). Sau đó, phạm vi trở nên trống và best là 4. Với x = 2^31 - 1, quá trình này cần 31 bước.

Thuật toán

Đặt lo = 0, hi = x và best = 0.
Khi lo ≤ hi, lấy mid = lo + (hi - lo) / 2.
Nếu mid × mid ≤ x (trong 64 bit), đặt best = mid và lo = mid + 1.
Nếu không, đặt hi = mid - 1.
Trả về best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Lỗi thường gặp và trường hợp biên

Bình phương trong 32 bit. Với x = 2147483647, giá trị mid đầu tiên là 1073741823, bình phương của nó xấp xỉ 1.15 × 10^18 và tràn thành một giá trị sai. Hãy nhân trong 64 bit hoặc so sánh m ≤ x / m.
Cùng lỗi tràn trong vòng lặp đếm: lần kiểm tra cuối cùng bình phương 46341, cho kết quả 2147488281, vượt giới hạn 32 bit.
Dùng cận trên loại trừ hi = x + 1. Với x lớn nhất, giá trị này là 2147483648, vượt quá giới hạn 32 bit một đơn vị.
Trả về giá trị mid được kiểm tra cuối cùng. Với x = 17, quá trình tìm kiếm kết thúc sau khi kiểm tra 5; đáp án là 4 đã được ghi nhớ.
Bắt đầu tìm kiếm từ lo = 1, khiến trường hợp x = 0 bị bỏ sót. Phép kiểm tra m ≤ x / m cũng chia cho 0 khi m = 0.

Câu hỏi thường gặp3

Độ phức tạp thời gian của thuật toán tìm căn bậc hai bằng tìm kiếm nhị phân là bao nhiêu?

Thời gian O(log x) và bộ nhớ O(1): mỗi bước giảm một nửa phạm vi, vì vậy x = 2^31 - 1 cần 31 bước. Đếm tăng dần từ 0 cần O(√x) bước, tức là 46340 bước với cùng giá trị x.

Phương pháp Newton tính căn bậc hai nguyên như thế nào?

Bắt đầu với r = x. Khi r × r > x, thay r bằng (r + x / r) / 2 bằng phép chia lấy phần nguyên. Mỗi bước đưa r giảm dần về phía căn bậc hai mà không vượt qua nó, và vòng lặp dừng tại phần nguyên của căn bậc hai. Với x = 2^31 - 1, cần 19 bước.

Tại sao lời giải cần số nguyên 64 bit khi đáp án chỉ cần 32 bit?

Đáp án tối đa là 46340, nhưng các ứng viên bạn kiểm tra thì không. Tìm kiếm nhị phân trong khoảng từ 0 đến x trước tiên thử một ứng viên gần 10^9, bình phương của số đó gần bằng 10^18, vượt xa giới hạn 32 bit khoảng 2.1 × 10^9.

def mySqrt(x):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

x = 17

Đầu ra mong đợi