30/09/2018, 18:13
Sắp xếp hàm theo tốc độ tăng
Em vừa học CTDL> nhưng mà đang lơ mơ lắm. Mọi người chỉ giúp em với
Đề bài là: Sử dụng big-O để sắp xếp các hàm dưới đây theo tốc độ tăng:
4n, 2^10, 4nlogn + n, 2^n, n^2 + 2n, nlogn, 2^(logn)
Bài liên quan
2^10 < 4n < nlogn < 4nlogn + n < n^2 + 2n < 2^logn < 2^n
Okie, thank. Nhưng mà cái hàm
2^logncó big-O là cái gì vậy bạn?Thì là O(2^log n) mà bạn.
Ối, mình quên mất. Cảm ơn nhiều nhé
2^logn lẹ hơn n^2 chứ, thậm chí lẹ hơn cả nlogn. 2^logn là tương đương với O(n) đó.
Mình có xem lại, 2^logn, nó còn nhẹ hơn cả n bạn ạ
Với f(n) = n, thì khi n tăng 10 lần, f(n) cũng tăng lên 10 lần. Còn f(n) = 2^logn chỉ tăng lên có 2 lần thôi
log ở đây ta tin là log cơ số 2 chứ ko phải cơ số 10…
Có lẽ mình nhầm một chút, nên xếp lại thành:
2^10 < 2^logn < 4n < nlogn < 4nlogn + n < n^2 + 2n < 2^n
Cảm ơn @tntxtnt @programmerit nhé