Độ phức tạp của thuật toán

Em có câu hỏi như vậy ai có thể giúp em với được không ạ. Em ngu về phần này thât sự ạ :(((
What will be the time complexity for following fragment of code? for(var i=0;i<n;i++) i*=k;

|A.O(n)
|B.O(k)
|C.O(lognk)
|D.O(logkn)

Ta có O(x) là độ phức tạp thuật toán ~ số vòng lặp for
lần lặp i >=n cũng ~ x độ phức tạp
để i>=n cũng như i=i*k cũng có nghĩa là k^x=n trở lên
suy ra x=logkn
Đáp án D.
P/s: Mình giảng giải hơi khó hiểu bạn thông cảm

3 Likes

lognk với logkn là cái gì vậy?

  • log của tích (=> 2 cái này giống hệt nhau)?
  • lognk = lognk và lognk = logkn?
4 Likes

Với k, n >= 1 thì i cũng phải >= 1. Như trên :slight_smile:

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?