设M是一个n行n列的0-1矩阵，每行的1都排在0的前面。 （1）设计一个最坏情况下O（nlogn)时间的算法找到M中含有1最多的行，说明算法的设计思想，估计最坏情况下的时间复杂度。 （2）对上述问题，能否找到一个最坏情况下O（n)时间的算法？
设M是一个n行n列的0-1矩阵，每行的1都排在0的前面。 （1）设计一个最坏情况下O（nlogn)时间的算法找到M中含有1最多的行，说明算法的设计思想，估计最坏情况下的时间复杂度。 （2）对上述问题，能否找到一个最坏情况下O（n)时间的算法？
参考答案和解析
AB
相关考题：
关于排序算法的以下说法，错误的是()A.归并排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)B.堆排序平均时间复杂度O(nlogn)，最坏时间复杂度O(nlogn)C.冒泡排序平均时间复杂度O(n^2)，最坏时间复杂度O(n^2)D.快速排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)
类比二分搜索算法，设计A分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，...，这样，或者找到要搜索的元素，或者把集合缩小到原来的1／k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此A分搜索算法在最坏情况下搜索成功的时间复杂度为(1)，在最好情况下搜索失败的时间复杂度为(2)。A．O(logn)B．O(nlogn)C．O(logkn)D．O(nlogkn)
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是(59)；该算法采用的设计方法是(60)。A．归并排序B．插入排序C．选择排序D．冒泡排序
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，在最坏情况下计算时间可以达到O(nlogn)的是( 58 )；A.归并排序B.插入排序C.选择排序D.冒泡排序
以关键字比较为基础的排序算法在最坏情况下的汁算时间下界为O(n1ogn)。下面的排序算法中，最坏情况下计算时间可以达到O(n1ogn)的是(33)；该算法采用的设计方法是(34)。A．归并排序B．插入排序C．选择排序D．冒泡排序
类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，……，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为(57)，在最好情况下搜索失败的时间复杂度为(58)。A．O(logn)B．O(nlogn)C．O(logkn)D．O(nlogkn)
以下有关算法的说法错误的是()。Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间；Ⅱ，在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法；Ⅲ.所谓最坏时间复杂度是指最坏情况下估算算法执行时间的一个上界；Ⅳ，同一个算法，实现语言的级别越高，执行效率就越低。A.ⅠB.Ⅰ和ⅡC.Ⅰ和ⅣD.Ⅲ
已知序列X={x1，x2，…，xm}，序列Y={y1，y2，…，yn}，使用动态规划算法求解序列X和Y的最长公共子序列，其最坏时间复杂度为（）。A、O（m*n）B、O（m+n）C、O（m*2n）D、O（n*2m）
问答题给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。