求Pascal大牛（表达能力好的）来！

对每个算法的实践怎样估算他的时间复杂度、空间复杂度

比如说排序中的冒泡、快排、堆排序（请举例），贪心与动规等如何根据数据范围分析选择（范围上下界最大可承受？）

 

空间复杂度，先学数据结构，然后手算，不同类型占空间不一样的，估算就行。

比如longint 4字节，integer 2字节，你开个ARR[1..100,1..100] OF LONGINT的数组就是开了100*100*4字节，一般，NOIP允许开50M，你不是玩动规的话是开不到50M的，所以你算都不要算.

时间复杂度，看循环乘起来，很好算的，也是估算啦。

举个例子：

插入排序、冒泡排序、选择排序的时间复杂度为O(n²)

因为他们都是双重循环的，N*N=n²

  for i:=1 to n-1 do begin

    for j:=I+1 to n do begin

    swap;

    end;

  end;

快速排序的时间复杂度为O(nlog₂n)，但快排遭遇有序序列是退化为O(n²)

冒泡的时间是N方J，时间复杂太大，我不用冒泡两年了

一般你可以根据FOR语句和WHILE，REPEAT语句等，估计复杂度，

递归的复杂度根据何时结束，几种情况估计，

也可以根据题目的意思估计。哪个实用用哪个

空间则根据开的数组等。longint 4字节，integer 2字节，这个可以根据类型范围估计空间

指针按题目的意思算空间，很费时，望采纳

举个例子：

7各种排序算法的比较

1.稳定性比较

 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的

 选择排序、希尔排序、快速排序、堆排序是不稳定的

2.时间复杂性比较

 插入排序、冒泡排序、选择排序的时间复杂性为O(n²)

 其它非线形排序的时间复杂性为O(nlog₂n)

 线形排序的时间复杂性为O(n);

3.辅助空间的比较

 线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);

4.其它比较

插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。

反而在这种情况下，快速排序反而慢了。

当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。

若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。

当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。

宜用归并排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

复杂度主要看循环次数即内外循环的嵌套次数。

看循环次数

例：选择排序o(n^2)

Dijkstra o（n^3）

时间看循环次数、 空间看定义的变量.....

这你最好还是看看有关《数据结构》的书吧，在课上这可是整整一节大课的内容，每种方法算的次数都不一样，一般的是时间复杂度、空间复杂度越高，这种算法也就越好想；反之，也就越难想出来。

推荐你本书：清华大学出版的《数据结构》

如以上问答内容为低俗/色情/暴力/不良/侵权的信息，可以点下面链接进行举报，我们会做出相应处理，感谢你的支持！

点此我要举报以上问答信息