كبير-O:لماذا التعقيد الزمني لهذه الحلقات هو O(N)؟

Question

لدي الوظيفة التالية.

int fun(int n) 
{ 
  int count = 0; 
  for (int i = n; i > 0; i /= 2) 
     for (int j = 0; j < i; j++) 
        count += 1; 
  return count; 
} 

لقد O(N) تعقيد الوقت.اعتقدت أنه O(N LogN)(أي.إذا قمنا بإزالة الحلقة الداخلية التي نحصل عليها)

for (int i = n; i > 0; i /= 2){
...
}

هذا هو O(Log N) أليس كذلك؟وتبين أن الحلقة الداخلية كذلك O(N) لأنها تزيد خطيا فقط.لذلك أعتقد أنه من المفترض أن يكون O(Log N * N).ما الخطأ الذي قد يحدث في تفكيري؟

Answer 1

انظر إلى عدد الخطوات التي تتخذها الحلقة الداخلية.إنه $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.ومع ذلك سلسلة هندسية أخبرنا:

$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^ك} = 2ن$$