Tính độ phức tạp thuật toán

Minh_Tran6 · February 10, 2022, 5:34pm

cho e hỏi độ phức tạp của hàm này tính như thế nào ạ?

rogp10 · February 11, 2022, 6:54am

A post was merged into an existing topic: Topic lưu trữ các post off-topic - version 3

Minh_Tran6 · February 11, 2022, 4:32am

Là tính O() của thuật toán ở trên ấy ạ

nguyenchiemminhvu · February 11, 2022, 7:00am

Theo như thuật toán bạn đưa ra thì giá trị của s sẽ nằm trong series:
0 1 3 6 10 15 21 28 … n

Với n:
n = 1 -------------- 1 loop
n = 2 -------------- 1 loop
n = 3 -------------- 2 loop
…
n = 10 ------------- 5 loop
n = xxx ------------ i loop

Mình không tìm được công thức độ phức tạp cụ thể cho phương trình trên, nên mình cho max boundary của nó là O(n), dù nó chỉ chạy i loop.

rogp10 · February 11, 2022, 7:33am

S_i = 1 + 2 + 3 + ... + i = \frac{i(i+1)}{2}
Thoát khỏi vòng lặp chỉ khi S_i > n vậy S_{i-1} \leq n.
Mà \forall n\geq 0\ \exists i \in \N^*,\ i(i-1) \leq 2n < i(i+1)
Từ đó suy ra i.