使用Kolmogorov不可压缩性方法的平均情况算法分析

Question

据说,不可压缩性方法简化了对平均情况的算法分析.据我所知,这是因为不需要为该算法计算所有可能的输入组合,然后得出平均复杂度.相反,将一个不可压缩的字符串作为输入.由于不可压缩的字符串是典型的,我们可以假设此输入可以作为平均情况的精确近似.

关于将不可压缩方法应用于算法,我很遗憾.顺便说一句,我不是数学家,但认为这个理论在日常编程中具有实际应用.

最后,我想了解如何推断出任何给定算法的平均情况,无论是微不足道的还是复杂的.有人可以向我演示如何将该方法应用于一个简单的算法吗？例如,给定一个输入字符串S,将所有唯一字符存储在S中,然后单独打印每个字符:

void uniqueChars(String s) {
    char[] chars = chars[ s.length() ];
    int free_idx = 0;

    for (int i = 0; i < s.length(); i++) {
        if (! s[i] in chars) {
           chars[free_idx] = s[i];
           free_idx++;
        }
    }

    for (int i = 0; i < chars.length(); i++) {
        print (chars[i]);
    }
}

只是为了争论.我认为伪代码就足够了.假设线性搜索以检查数组是否包含元素.

当然,可以接受更好的算法来证明理论是可以接受的.

这个问题可能是荒谬的,也是不切实际的,但我宁愿提出要求而不是误解.

Answer 1

复制我对CS.Se 问题的回答，以供相互参考

1. 柯尔莫哥洛夫复杂性（或算法复杂性）处理“字符串”的最佳描述（一般意义上的字符串作为符号序列）

2. 如果字符串的（算法）描述（柯尔莫哥洛夫复杂度K）不小于其（文字）大小，则该字符串（足够）不可压缩或（足够）算法随机。换句话说，字符串的最佳描述是字符串本身。

3. 该理论的主要结果是，大多数字符串（在算法上）是随机的（或典型的）（通过 Chaitin 的工作，这也与其他领域有关，例如哥德尔定理）

4. 柯尔莫哥洛夫复杂度与概率（或香农）熵有关，实际上熵是 KC 的上限。这将基于描述复杂性的分析与基于概率的分析联系起来。它们可以互换。

5. 有时使用概率分析可能更容易，其他描述性复杂性（可以说相同的观点）

因此，根据上述情况，假设算法随机输入算法，则假设如下：

1. 输入是典型的，因此分析描述了平均情况（上面的第 3 点）
2. 输入大小以某种方式与其概率相关（上面第 2 点）
3. 人们可以从算法观点转向概率观点（上面第 4 点）