第5课时间复杂度和空间复杂度

405794672

我只是不明白举的两个例子。一个是算法判断闰年，第二个是列出2050个元素的数组。
说是第二个以空间换取时间。我怎么觉得这个是增加了空间又增加了时间呢？
难道说a[2049]，CPU不是从0开始一个一个地搜到2049吗？这不是搜了2050次才能调出a[2049]的元素来使用吗？

lhgzbxhz

数组在内存中是一段连续的空间
例如声明一个int类型的数组
那么数组变量中保存的就是数组中第一个变量的地址，假设这个变量是a
那么a[2049] CPU实际干的是:内存(a+2049×sizeof(int))中的值

405794672

lhgzbxhz 发表于 2020-7-8 15:46
数组在内存中是一段连续的空间
例如声明一个int类型的数组
那么数组变量中保存的就是数组中第一个变量的 ...

对啊，我也是这意思啊！我问题是另一个，是它访问这个地址处的值时，要从前面往后依次搜索。你意会错了，我不是说比较里面的值，说的是数数，看门牌号。从1号一直跑到2050号处，才敲门进去。

lhgzbxhz

405794672 发表于 2020-7-8 17:07
对啊，我也是这意思啊！我问题是另一个，是它访问这个地址处的值时，要从前面往后依次搜索。你意会错了， ...

不是这样的，CPU不像门牌号那样，它更像是一个大箱子，前面通过计算可以算出2050号物品在哪里，知道它在哪里就可以伸手去拿了，根本不需要从1开始逐个跑

lhgzbxhz

举个例子，声明一个数组：int array[2050];
假设数组第一个元素（下标为0）的内存地址是0012FF58（16进制）
那么最后一个元素（下标为2049）的内存地址就是0012FF58 + 2049 * sizeof(int) = 0012FF58 + 8196(十进制)(即16进制的2004) = 00131F5C
知道这个内存地址后就可以取出值了，怎么还要从1开始一个一个跑呢？

永恒的蓝色梦想

你坐火车，难道会去第一个车厢从前向后找自己的座位？

405794672

永恒的蓝色梦想 发表于 2020-7-8 22:08
你坐火车，难道会去第一个车厢从前向后找自己的座位？

火车停下时你在第一节车厢位置，难道你不是走到自己的车厢才上车？

lhgzbxhz

405794672 发表于 2020-7-9 08:45
火车停下时你在第一节车厢位置，难道你不是走到自己的车厢才上车？

这个比喻不恰当，你还是看我的说法

永恒的蓝色梦想

405794672 发表于 2020-7-9 08:45
火车停下时你在第一节车厢位置，难道你不是走到自己的车厢才上车？

楼上老哥说得对，这个比喻确实不恰当……

java2python

lhgzbxhz 发表于 2020-7-9 09:11
这个比喻不恰当，你还是看我的说法

甚至是为了避免列车突然关门，刚好遇上第一节，就先进列车再说。。。
当然比喻其实意思懂了就行。。。

405794672

lhgzbxhz 发表于 2020-7-9 09:11
这个比喻不恰当，你还是看我的说法

你的比喻更不恰当啊。因为行不通啊！我的好歹行得通

405794672

lhgzbxhz 发表于 2020-7-8 18:42
不是这样的，CPU不像门牌号那样，它更像是一个大箱子，前面通过计算可以算出2050号物品在哪里，知道它在 ...

假如你的箱子里有2050个格子，你能一眼瞄出第2010个格子在哪里吗？你还不得一个一个数着过去，不是吗？

lhgzbxhz

405794672 发表于 2020-7-10 19:08
假如你的箱子里有2050个格子，你能一眼瞄出第2010个格子在哪里吗？你还不得一个一个数着过去，不是吗？

是算出来的，又不是数出来的，比喻不重要，你看看5楼

405794672

lhgzbxhz 发表于 2020-7-11 08:43
是算出来的，又不是数出来的，比喻不重要，你看看5楼

算出来你也得找到吧?几楼我都看了。说的不是同一个问题。算只能算出来在哪个编号。但是你要取东西必须一个一个地数。我说的是算出来之后的事，是实际要取的东西。

lhgzbxhz

405794672 发表于 2020-7-11 09:45
算出来你也得找到吧?几楼我都看了。说的不是同一个问题。算只能算出来在哪个编号。但是你要取东西必须一 ...

取东西不用数啊~你知道一个地址就可以取了，干嘛要数？
而且算出来的不是编号，是内存地址