基于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上复制我的答案。这个问题，用于相互参考

1. Kolmogorov复杂度(或Algorithmic复杂度)处理"字符串"的最优描述(一般意义上的字符串是符号的序列)

2. 字符串(充分)不可压缩或(充分)算法随机如果它的(算法)描述(kolmogorov复杂度K) 不小于它的(文字)大小。换句话说，字符串的最佳描述，就是字符串本身。

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

4. Kolmogorov复杂度与Probabilistic(或Shannon) Entropy有关，实际上熵是KC的上界，这将基于描述复杂度的分析与基于概率的分析联系起来。

5. 有时使用概率分析可能更容易，有时使用描述性复杂性(例如相同的视图)

因此，根据上述，假设算法的随机输入，我们假设如下:

1. 输入是典型的，因此分析描述了平均情况的场景(上面第3点)
2. 输入的大小在某种程度上与其概率(上文第2点)
有关
3. 可以将从算法视图传递到概率视图(上面第4点)