كبير-O:لماذا التعقيد الزمني لهذه الحلقات هو O(N)؟
-
29-09-2020 - |
سؤال
لدي الوظيفة التالية.
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)
.ما الخطأ الذي قد يحدث في تفكيري؟
المحلول
انظر إلى عدد الخطوات التي تتخذها الحلقة الداخلية.إنه $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ن$$
لا تنتمي إلى cs.stackexchange