-
So it's certainly at least linear in the length of the list. For each starting point, what do I do?
它至少是线性的计算列表的长度,每次到了循环开始的点？
-
If it was an unordered list, we were basically stuck with linear search. Got to walk through the whole list to see if the thing is there.
如果是一个未排序的列表,基本上我们就只能使用线性搜索了,通过遍历整个列表来查看。
-
Because if you did what I suggested with the list, the time to look up the key would be linear in the length of the list. You'd have to look at each element until you found the key.
字典是用一种很神奇的，叫做散列法的算法,来实现的，后面我们将,会学到一点关于。
-
That one's not so obvious. So let's think about this for a second. To sort a list in linear time, would say, I have to look at each element in the list at most a constant number of times.
所以让我们来思考一会,要在线性时间能排序，列表里每个元素最多被使用常数次,不一定是一次，对吧。
-
Right? If that was the case in that code, then my complexity is no longer log, because I need linear access for each time I've got to go to the list, and it's going to Lisp be much worse than that.
这里的复杂度不再是对数的了，因为每次在列表中，查找需要线性访问,可能还要糟糕,其实，有些编程语言，如。
-
If I look for, say, minus 1, you might go, gee, wait a minute, if I was just doing linear search, I would've known right away that minus one wasn't in this list, because it's sorted and it's smaller than the first elements.
如果我要查找-1，你可能要怒了，呵呵，等一等，如果我用的是线性查找，我不会知道-1不在这个列表中,但是列表是排好序的,1又比第一个元素小。
-
Well let's see. My fall back is, I could just do linear search, walk down the list one at a time, just comparing those things. OK. So that's sort of my base. But what if I wanted, you know, how do I want to get to that sorted list? All right?
我只能做线性搜索了,一次遍历一遍列表，一个一个比较，但如果我想要,那怎样得到有序的列表呢？,现在的一个问题是，我们排序之前？
-
All right? A linear search, I start at the beginning of the list and walk all the way through it. All right, if I'm lucky and it's at the low end, If it's not, if it's at the far end, I've got to go forever, and you saw that last time where this thing paused for a little while while it actually searched a list this big.
如果很幸运就在开头,那运行起来很快，如果是在末尾,那就一直得走到头，上次看到了,如果搜索空间很大,程序都会暂停一会,好的，那我希望你们。
-
You try to design actually I'm going to come back to that in a second. It's like you're trying to use a hash function that spread things out pretty evenly. But the places you store into in those lists may have to themselves have a small list in there, and when you go to check something, you may have to do a linear search through the elements in that list.
你尝试着去设计,实际上过会儿我会回头讲解这个问题,类似于你需要用一个哈希函数,非常平均的将物体分发出去,但是在列表中你数据,映射到的地方可能会有自己的一小段列表，当你回头查找数据的时候,你可能需要在那一小段列表中做线性查找。
-
I've got to count my way down, which means that the access would be linear in the length of the list to find the i'th element of the list, and that's going to increase the complexity.
的位置并去访问，然后继续下去，也就意味着,找到数组中的第i个元素的方法,是关于数组的长度呈线性复杂度的，这回增加算法的复杂度。
-
I could still do the linear case, which is order n or I could say, look, take the list, let's sort it and then search it. But in that case we said well to sort it was going to take n log n time, assuming I can do that.
我仍然可以做O的线性搜索,或者也可以以这个列表为例，我们先将其进行排序,然后再进行查找，但是在这种情况下,要花费n，log，n的时间去对其进行排序。
应用推荐