提问人：terrabyte 提问时间：11/25/2022 更新时间：11/25/2022 访问量：51
Mairson的筛分空间复杂性
Mairson's Sieve Space Complexity
问：
在论文《素数生成的一些新上限》中，Mairson 概述了以下算法
他还说，该算法必须以 2N logN 为代价存储双向链表，从而产生 O（N logN） 空间复杂度。但是，从这个算法来看，它只存储了 3 个大小为 O（N） 的数组。这个 log（N） 项从何而来？
答：
4赞
oluckyman
11/25/2022
#1
Mairson的论文主要关注计算N以内的素数的比特复杂度。因此，O（N） 字的空间复杂度等价于 O（N log N） 位，因为存储在字中的数字具有 O（N） 大小，因此需要 O（log N） 位。（你会注意到他的符号中大 O 的 B 下标。B 表示位复杂度。
评论