时间戳

首页 > 解决方案 > 更好地理解 (log n) 时间复杂度

algorithm - 更好地理解 (log n) 时间复杂度

问题描述

我对（log n）有点困惑。鉴于此代码

public static boolean IsPalindrome(String s) {
    char[] chars = s.toCharArray();
    for (int i = 0; i < (chars.length / 2); i++) {
        if (chars[i] != chars[(chars.length - i - 1)])
            return false;
        }
        return true;
    }
}

我正在循环 n/2 次。因此，随着 n 长度的增加，我的时间增加了 n 时间的一半。在我看来，我认为这正是 log n 是什么？但是写这段代码的人说这仍然是O(N)。

在什么情况下循环，可以是（log n）吗？例如这段代码：

1. for (int i = 0; i < (n * .8); i++)

这是日志n吗？我正在循环 n 长度的 80%。

这个如何？

2. for (int i = 1; i < n; i += (i * 1.2))

那是日志n吗？如果是这样，为什么。

标签： algorithmperformancetime-complexitybig-o

解决方案

1. for (int i = 0; i < (n * .8); i++) 在第一种情况下，基本上你可以用另一个变量替换 0.8n，我们称之为 m。

for (int i = 0; i < m; i++)您正在循环 m 次。您i在每次迭代中增加一个单位的价值。由于m和n只是变量名，因此上述循环的 Big-O 复杂度为 O(n)。

2. for (int i = 0; i < n; i += (i * 1.2)) 在第二种情况下，您不会增加 的值i，而 的值i始终是0。这是for-infinite循环的经典案例。

您正在寻找的是2. for (int i = 1; i <= n; i += (i * 1.2))在这里，您正在以对数方式递增 i 的值（但不是以 2 为底）。

考虑for (int i = 1; i <= n; i += i)每次迭代后 i 的值加倍。i 的值将是1, 2, 4, 8, 16, 32, 64..假设 n 值为 64，您的循环将在 7 次迭代中终止，这是(log(64) to the base 2) + 1（+1因为我们从 1 开始循环）操作数。因此它变成了对数运算。

2. for (int i = 1; i <= n; i += (i * 1.2))在您的情况下，解决方案也是对数解决方案，但它不是以 2 为底的。您的对数运算的底是2.2，但在大 O 表示法中，它归结为O(log(n))

推荐阅读