使用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]);
    }
}

仅就论证而言，我认为伪代码已足够。假设使用线性搜索来检查数组是否包含一个元素。

当然，如果有更好的算法可以用来展示理论，那就更好了。

这个问题可能毫无意义且不切实际，但我宁愿提出来而不是抱有误解。

- user3813812

---

你可能想查看这篇论文的例子，来了解此方法的应用。（http://homepages.cwi.nl/~paulv/papers/sorting.pdf）但我不得不思考你在这里的目标是什么。你有一个算法需要分析时间运行吗？顺便说一句，你提供的代码可能很难分析，因为`Set.add`的运行时间取决于`Set`的实现方式。 - murgatroid99

这个问题可能更适合发布在计算机科学 Stack Exchange上。 - Barranka

我的目标是学习如何应用不可压缩方法进行平均运行时间分析。这只是个人学习的一部分，而不是迫切需求。 - user3813812

murgatroid99，你是指这个链接吗？http://homepages.cwi.nl/~paulv/course-kc/Tao-AverageNotes.pdf - user3813812

在CS StackExchange上提出了类似的问题：http://cs.stackexchange.com/q/35622/26108 - user3813812

Answer 1

为了相互参考的目的，我在CS.Se问题上重述了我的答案。

科尔莫戈罗夫复杂性（或算法复杂性）涉及“字符串”的最优描述（在一般意义下，指作为符号序列的字符串）。

如果一个字符串是（足够）不可压缩的或（足够）算法随机的，则其（算法）描述（科尔莫戈罗夫复杂度K）不小于其（字面）大小。换句话说，该字符串的最佳描述是字符串本身。

该理论的主要结果是，大多数字符串都是（算法上）随机的（或典型的）（这也与哥德尔定理相关，通过柴廷的工作实现）。

科尔莫戈罗夫复杂性与概率（或香农）熵相关，事实上熵是KC的上界。这将基于描述复杂度的分析与基于概率的分析联系起来。它们可以互换使用。

有时使用概率分析可能更容易，而其他时候则使用描述复杂度（可以说是相同的观点）。

基于上述情况，假设一个算法随机输入另一个算法，那么可以做出以下假设：

1. 输入是典型的，因此分析描述了平均情况场景（上面第3点）
2. 输入大小与其概率有一定关系（上面第2点）
3. 可以从算法视角转换为概率视角（上面第4点）

- Nikos M.