algorithm - 使用 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 question 上复制我的回答, 供相互引用

1. Kolmogorov Complexity(或Algorithmic Complexity)处理“字符串”的最佳描述(一般意义上的作为符号序列的字符串)

2. 一个字符串(足够)不可压缩或(足够)算法随机如果它的(算法)描述(kolmogorov comlplexity K ) 不小于其(文字)大小。换句话说，字符串的最佳描述是字符串本身。

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

4. Kolmogorov Complexity 与概率(或香农)熵有关，实际上熵是 KC 的上限。这将基于描述性复杂性的分析与基于概率的分析联系起来。它们可以互换。

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

因此，鉴于上述情况，假设对算法进行算法随机输入，则假设如下:

1. 输入是典型，因此分析描述的是平均情况(上述第 3 点)
2. 输入大小以某种方式与其概率相关(上面第 2 点)
3. 可以通过从算法 View 到概率 View (上述第 4 点)