穷举复杂度为o(2^n),n为位数
针对8位，16位时间可以接受，但是32位的时间不可接受了
昨天菜农提到会改变初值的问题，实际上成也初值败也初值，利用初值有望将复杂度降为o(n^2)（猜测）
crc计算的本质：
输入一个crc值，即in_crc。输入当前要计算的位，即bit。根据多项式值,poly，求得输出crc值，即out_crc。
poly是固定的，in_crc,bit,out_crc这三个数知道任意两个可以求出第三个数（poly要满足菜农的条件）
我认为复杂度有望降为o(n^2)的依据是
现有两个位0b10，如果将这两个bit交换，则会改crc结果，如果要结果不变，则要改变初值。这个初值的改变量只需要知道一个位即可求出来
同理，经过m次交换后将离散的位合并到一起，按常规方法求出，即得答案
不用穷举求解的前提是红色的字条件成立
|
楼主
