c - 一个简单算法的时间复杂度

Question

你好，抱歉我的英语不好。

我仍在尝试估计以下算法的复杂性。

有:

int f = 1, n, x, licznik = 0;
printf("Variable of n: ");
scanf("%d", &n);
printf("Variable of x: ");
scanf("%d", &x);

while(n > 0) {
        if(n%2 == 0) {
                x = x*x;
                n = n/2;
                licznik++;
        }
        else {
                f = f*x;
                n = n-1;
                licznik++;
        }
}

我的观察:

当 n =/then/licznik =

n = 0l = 0

n = 10l = 5

n = 100l = 9

n = 1000l = 15

n = 10000l = 18

n = 1 000 000l = 26

所以它仍在增长，但非常缓慢。所以它看起来像一个“log n”函数。这个算法的时间复杂度是 O(log n) 是一个很好的答案吗？最好的选择和最坏的选择呢？感谢您的帮助。

PS:“licznik”是一些乘法。

Answer 1

如果 n 是一个奇数，你总是将它减一，使它成为偶数并保证它在下一次迭代中被分成两半。

在最坏的情况下，您会得到 2*log n，即 O(log n) 复杂度。