Hỏi hướng giải bài code không dùng đệ quy

[Nguyen_Phuc_Tien]

Thầy có nói có thể dùng Stack hoặc Queue. Nhưng e vẫn cho hiểu bài này lắm
Nhờ mn gợi ý hướng giải hoặc từ khóa để tham khảo các dạng bài này ạ.

[rogp10]

Push n vào stack rồi tính thôi

[kisuluoibieng (Tên Gì Cũng Được)]

Thì dùng for thôi, rồi lưu giá trị vào mảng T thôi

[HR16 (Gà Coder)]

Không dùng đệ quy thì ta dùng quy hoạch động, dùng như thế nào thì mấy thím trên có nói rồi đó

[tntxtnt]

\begin{aligned} T(n) &= aT\left(\frac{n}{2}\right) + n^k \\ &= a\left(aT\left(\frac{n}{4}\right) + \left(\frac{n}{2}\right)^k\right) + n^k \\ &= a^2T\left(\frac{n}{4}\right) + a\left(\frac{n}{2}\right)^k + n^k\\ &= a^3T\left(\frac{n}{8}\right) + a^2\left(\frac{n}{4}\right)^k + a\left(\frac{n}{2}\right)^k + n^k\\ &= ... \\ &= a^mT\left(\frac{n}{2^m}\right) + a^{m-1}\left(\frac{n}{2^{m-1}}\right)^k + ... + a^2\left(\frac{n}{4}\right)^k + a\left(\frac{n}{2}\right)^k + n^k\\ \end{aligned}

Cho \dfrac{n}{2^m} là số lẻ thì T\left(\dfrac{n}{2^m}\right) = \left(\dfrac{n}{2^m}\right)^k. Vậy:

\boxed{T(n) = a^m\left(\frac{n}{2^{m}}\right)^k + a^{m-1}\left(\frac{n}{2^{m-1}}\right)^k + ... + a^2\left(\frac{n}{4}\right)^k + a\left(\frac{n}{2}\right)^k + n^k}

rồi dùng vòng for tính thôi :V

[noname00 (HK boy)]

Nghịch ngợm comment của cụ @tntxtnt xíu, sai thì thôi

\begin{aligned} T(n) &= \sum_{i=0}^{m} a^i \left(\frac{n}{2^i}\right)^k\\ &= n^k \sum_{i=0}^{m} \left(\frac{a}{2^k}\right)^i\\ &= n^k \left(\left(\frac{a}{2^k}\right)^{m+1} - 1\right) \left(\frac{a}{2^k} - 1\right)^{-1} \end{aligned}

O(log n + k)