算法复杂度混乱(algorithm complexity confusion)
for(int i=0; i<n; i++) { blah; }
for(int i=0; i<n; i++) { blah; }
<==这有一个复杂的O(n)然而,如果你知道n在手之前不会是复杂性变成O(1),我的意思是我可以写出指令3次。
blah; blah; blah;
如果你在运行程序之前不知道n有多大,那么就不可能用后一种方式写下指令。
如果我有错误,请澄清我的误解。
for(int i=0; i<n; i++) { blah; }
<== this has a complexity of O(n)however if you know n to be 3 before hand won't the complexity become O(1), I mean i could just write out the instructions 3 times.
blah; blah; blah;
whereas if you don't know how big n is before you run the program then it's not possible to write down the instructions in the latter way.
Please clarify my misconception if I have it.
原文:https://stackoverflow.com/questions/20193866
最满意答案
在示例中,在第13行,我将i:= 2更改为i:= 1并且代码奇迹般地起作用。 为什么?!
In the sample, on line 13, I changed i:=2 to i:=1 and the code miraculously works. Why?!
相关问答
更多-
您的新复杂性仍然是二次的 ,因为您需要向右移动所有已排序的部分。 因此,使用二分搜索只是稍微好一点。 我建议对大型数组使用快速排序算法(在O(n log n)时间内),二次插入排序算法仅适用于小型数组。 Your new complexity is still quadratic, since you need to move all of the sorted parts rightward. Therefore, using binary search is only marginally better ...
-
二进制插入排序用作插入排序,但它将插入点与实际插入的位置分开。 为数组实现的插入排序将在定位插入点的同时移动项目。 在循环浏览项目以查找插入点时,它还会移动项目以便为插入腾出空间。 二进制插入排序将利用已排序的项目进行排序的事实,因此它可以使用二进制搜索来查找插入点。 由于二进制搜索也不能移动项目以便为插入腾出空间,因此必须在找到插入点之后在单独的步骤中完成。 您想要解释的代码是移动项目以便为插入腾出空间的代码。 Binary insertion sort works as insertion sort, ...
-
使用c中的链表代码进行此插入排序有什么问题?(What is wrong with this insertion sort using linked list code in c?)[2023-08-19]
第6行形成最后一行 if (prevptr=NULL) 它应该是 if (prevptr==NULL) 单个“=”执行赋值而不是比较。 The 6th line form last if (prevptr=NULL) it should be if (prevptr==NULL) Single "=" does the assignment instead of comparison. -
似乎每次你应该交换迭代器这两个元素时,你都会在itr和jtr之前向容器中添加元素。 for(auto itr = newSongList.begin(); itr != newSongList.end(); ++itr) { for(auto jtr=itr; jtr != newSongList.begin(); --jtr){ cout << itr->GetTitle() << " " << jtr->GetTitle() << endl; // if s1 ...
-
在示例中,在第13行,我将i:= 2更改为i:= 1并且代码奇迹般地起作用。 为什么?! In the sample, on line 13, I changed i:=2 to i:=1 and the code miraculously works. Why?!
-
二进制插入排序算法(binary insertion sort algorithm)[2022-01-16]
首先要突出的是: while (left=a[middle]) left=right+1; else right=middle; 你想要left = middle + 1 。 该代码适用于我的改变。 First thing that stands out is here: wh ... -
如果使用有间隙的数组和二进制搜索来确定插入内容的位置,则很有可能排序为O(n log(n)) 。 有关详细信息,请参阅https://en.wikipedia.org/wiki/Library_sort 。 然而,这并不像广泛实施的各种其他种类那样有效。 所以这些知识只是理论上的兴趣。 If you use a gapped array and a binary search to figure out where to insert things, then with high probability y ...
-
您过早地执行以下任务: data[atas] := temp; 在循环的下一次迭代中, k-1的值将变为atas ,因此错误的值将被复制到data[k] ,从而导致重复并丢失data[atas]中的原始值。 因此,将该行移出循环:仅在移位操作完成时才需要执行: while (k > atas) do begin data[k] := data[k - 1]; k-=1; end; data[atas] := t ...
-
就地插入排序比创建新列表的插入排序慢?(Inplace insertion sort slower than insertion sort that creates a new list?)[2021-10-10]
第一个你做了很多工作。 当您找到插入点时,然后您不断交换项目以将项目从[i]移动到[j] 。在第二个中,您使用insert功能将项目插入到第二个阵列中。 这只是将数组中的所有内容都向下移动一个。 换句话说,你在第一个插入是这样的: while i > j temp = sequence[i] sequence[i] = sequence[i-1] sequence[i-1] = temp i = i-1 因此,您对项目必须移动的每个位置执行四次数组访问和三次分配。 在第二个 ... -
插入排序错误列表索引(Insertion sort error list index)[2023-08-07]
问题是arrayInsertion[i + 1]当i = 7然后i超出界限,因为列表中只有7元素。 你也不记得当前的价值和指数。 for i in range(1, len(arrayInsertion)): curr = arrayInsertion[i] pos = i while pos > 0 and arrayInsertion[pos - 1] > curr: arrayInsertion[pos] = arrayInsertion[pos - 1] ...