必考题

望岳

2021-09-12 11:35:00

比之前听的课更好懂

0 0

云散兮

2021-09-11 10:00:00

云里雾里地听完了……

0 0

墨色槐

2021-09-09 19:25:00

我想咨询一下产品经理对技术的要求有多高呢？请问数据科学专业投递平台型产品经理是否合适呢？我是海外留学生，并没有相关的产品实习经验，本科时期的实习经历也很少，都是会计师事务所的事情，感觉对这个岗位应聘没有任何帮助。由于今年疫情原因现在还在国外也没办法回去进行实习，现在秋招就快开始了真的很焦虑了

0 0

咸鱼王

2018-10-13 14:26:13

c：逆序时，时间复杂度为O(N)

d:他一定会从头到尾比较一次的，所以O(N*N)

b:有序数列，可以减少比较次数

a:如果选择增量为1，则只需要一n比较。这个欢迎补充，说得不好

0 0

岁月长歌

2018-10-13 14:26:00

归并排序中的merge是

int[] temp=new int[e-s+1];

如果前部分的首元素大于后部分的最后元素要大，那么只需要比较n/2，即可完成排序

0 0

子不语

2018-10-13 14:25:42

说起归并算法，我不说概念性的东西。举个例子就可以看出来了

原数列：6 202 100 301 38 8 1

第一次：{6 202 }，{100 301}，{8 38}，{1} 比较3次 6和202 100和301 38和8

第二次：{6 100 202 301}，{1 8 38} 比较4次 6和100 100和202 202和301 1和8

第三次：{1 6 8 38 100 202 301} 比较4次 1和6 6和8 8和100 38和100

则总共比较次数是 3+4+4=11次

如果序列是 1 6 8 38 100 202 301

第一次：{1 6}，{8 38}，{100 202}，{301} 比较3次

第二次：{1 6 8 38}，{100 202 301} 比较4次

第三次：{1 6 8 38 100 202 301} 比较4次

总共11次

如果序列是 301 202 100 38 8 6 1

第一次：{202 301}，{38 100}，{6 8}，{1} 比较3次

第二次：{38 100 202 301}，{1 6 8} 比较3次

第三次：{1 6 8 38 100 202 301} 比较3次

总共是9次

则可以说明归并排序的比较次数和序列的初始顺序有关

0 0

冬季恋歌

2018-10-13 14:25:12

直接插入排序很明显，在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；

折半插入排序，比较次数是固定的，与初始排序无关；

快速排序，初始排序不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分次数，所以会影响总的比较次数；

归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关。

0 0

人间喜剧

2018-10-13 14:24:55

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

0 0

资深90后

2018-10-13 14:24:45

选择排序无视队列原来是否有序，他自己都会再排一遍，所以它的时间复杂度一直是最差的O（n2），最好情况和最差情况一样

0 0

碎梦不是梦碎

2018-10-13 14:24:29

我能肯定的是D，但是不理解B。我仔细想了一下。

关于归并可以这么解释。首先归并排序中 merge的任务是把两个有序数组合并为一个有序数组。假设A，和B为两个有序数组,合并为一个有序数组C，最好情况比较n/2次（n为数组C的长度，假设数组A和数组B等长，都为n/2）,这种情况的前提条件是数组A中最小的元素比数组B中最大的元素要大。那么只要A[0]和B中所有元素都比较过一遍以后，数组A中的其他元素就不用比较了，所以比较了n/2次。最坏情况元素错落，A[0]和B[0]比，假设得出A[0]以后，A[0]先和B[1]比，B[1]再和A[1]比,A[1]再和B[2]比..........那就是n-1次。不知道自己分析的对不对，还是有点疑惑。我的疑惑是归并算法它的时间复杂度不管最好最坏都是一样的O（nlogn），它和比较次数难道没有关系吗？求大神回答。

0 0