小编Edw*_*tle的帖子

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

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

最后,我想了解如何推断出任何给定算法的平均情况,无论是微不足道的还是复杂的.有人可以向我演示如何将该方法应用于一个简单的算法吗？例如,给定一个输入字符串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]);
    }
}

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

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

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