一个朋友的面试题（有兴趣者请进） ( 积分: 0 )

to 楼上的：
不加额外的存储空间指的是不能新建数组、链表等大小与N有关的空间，常量级的空间，比如交换A、B变量的第三变量temp，或者循环控制变量i之类的，都是可以用的。

数组是什么样子的 有规律么？有界值么？

没，随机的

首先说明，这并不是解。
只是我为交换作为约束条件的算法，时间复杂度比O大。
var
a: array of Integer;
Num, Half, SwapTimes: Integer;
procedure Swap(x, y: Integer);
var Temp: integer;
begin
Temp := a[x];
a[x] := a[y];
a[y] := Temp;
Inc(SwapTimes);
end;

procedure SwapStep(i, Step: Integer);
begin
Swap(i, i + Step);
end;

procedure TForm1.Edit1Exit(Sender: TObject);
begin
Num := StrToInt(TEdit(Sender).Text);
Half := (Num + 1) div 2;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
Edit1.Text := '100';
ActiveControl := Edit1;
end;

procedure TForm1.Button1Click(Sender: TObject);
procedure Sort(aStart, aTo: integer);
var
i, Step: Integer;
begin
Step := (aTo - aStart - 1) div 4 * 2 + 1;
for i := 0 to (aTo - aStart + 1) div 4do
SwapStep(aStart + i * 2, Step);
if aTo - aStart > 3 then
begin
if (aTo - aStart + 1) mod 4 = 0 then
SwapStep((aStart + aTo) div 2, 1);
Sort(aStart, aStart + Step - 2);
Sort(aTo - Step + 2, aTo);
end;
end;
{ procedure Sort2(aStart, aTo: integer);
var
i, Step: Integer;
begin
Step := (aTo - aStart + 1) div 4 * 2 + 1;
for i := 0 to (aTo - aStart - 1) div 4do
SwapStep(aStart + i * 2, Step);
if aTo - aStart > 1 then
begin
Sort2(aStart, aStart + Step - 2);
Sort2(aTo - Step + 2, aTo);
end;
end;
}
var
i: integer;
TempStr: String;
begin
if Num < 2 then
Exit;
SwapTimes := 0;
a := nil;
SetLength(a, Num + 1);
for i := 1 to Numdo
a := i;
Sort(2, Half * 2 - 1);
// Sort2(2, Half * 2 - 1);
TempStr := IntToStr(SwapTimes) + ' > ';
for i := 1 to Numdo
TempStr := TempStr + Format('%3d', [a]);
Memo1.Lines.Add(TempStr);
end;

其中 Sort1 用的交换次数较少，而 Sort2 用的时间可能较少。
用的是 交换定长，反中序二叉递归算法。

什么是时间复杂度？如果说，不使用多重循环时间复杂度就是0,那楼主的问题用
100*100个if语句顺序下来肯定能搞定。

整数的个数也是不定的，100个只是举例子，所以100*100个if语句是行不通的。

作者的意思就是把一个数组中奇数不改变顺序放在前面，偶数放在后面
大伙都想得太复杂了，其实可以简单一点去解决。
举例：
1,2,4,6,7,8,9结果为1,7,9 2,4,6,8对吧
解决思想：
奇数的位置应该是当前位置－前面的偶数个数
1.i从1到n遍历
2.设置偶数个数计数count=0及最前面的位置pos=-1
2.如果该数为奇数，那么其位置为i-count,将其放到正确的位置i-count上，并且将pos到i-1的偶数全部后移一位（pos到i-1应该全是偶数）
3.如果该数为偶数，计数count:=count+1
算法如下:
procedure OddEvenDeal(piInteger;ACount:Integer);
var i,EvenPos,EvenCount,SaveInt:integer;
tmppiInteger;
begin
EvenPos:=-1;
EvenCount:=0;
tmppi:=pi;
for i:=0 to ACount-1do
begin
if (tmppi^ mod 2)=1 then
//奇数
begin
if i<>i-EvenCount then
//位置不同才处理
begin
SaveInt:=tmppi^;
MoveMemory(Ptr(Integer(pi)+sizeof(Integer)*(EvenPos+1)),
Ptr(Integer(pi)+sizeof(Integer)*EvenPos),EvenCount*sizeof(Integer));
(PInteger(Integer(pi)+sizeof(Integer)*EvenPos))^:=SaveInt;
Inc(EvenPos);
end;
end
else
//偶数
begin
if EvenPos=-1 then
EvenPos:=i;
Inc(EvenCount);
end;
Inc(tmppi);
end;
end;

楼上的算法看起来是O的，其实还是O(n^2)的
即使使用MoveMemory,它的时间复杂度还是O，并不是说只有一句就是O(1)

呵呵，不懂windows机制了吧
movememory和交换两个数没有什么分别，不能算O,呵呵
拷贝内存就是一个指令就能完成的事，与n没有关系，n=1还是n=1000都是一个速度

拷贝内存可不会一个一个字节的拷，你研究研究内存管理就知道了

movememory确实可以大幅度优化执行速度，但在怎么优化，时间也不可能是O(1)的，除非它只是简单复制了数组的头指针，那样显然是会出错的。也许n=1和n=1000是一个速度，但是n=1000000呢？再大点呢？

lijun4183: movememory是利用了汇编级(机器代码)的一种循环,严格的说,时间复杂度仍然
是O,不管你这个O比别人的O快多少,从理论上讲,仍然是O.所以,整个算法就是
O(n^2),而不是O

不知道此题是否有解,如果有,一定很巧妙.

呵呵，加上条件一个纯数学问题，从算法的角度考虑
o，关注

SS2000 不同意你的说法，movememory汇编级的循环。
编译器不会将其翻译成汇编循环的，呵呵，一般内存拷贝都是基于页的
所以小于页大小的拷贝速度都一样。当然AI_Player说的n=1000000例外,呵呵

lijun4183：
MOV ESI,EAX //源地址
MOV EDI,EDX //目的地址
MOV EAX,ECX //长度
REP MOVSD //拷贝指令，这就是循环

简单的说，以上是movememory中的核心代码，可以看出，是用了REP MOVSD这个
指令，REP就是一个汇编级的循环，循环次数当然就是长度了。所以，这个和页
面拷贝没有关系，无论什么操作系统，最终还是要用汇编，机器码来实现的。

跑题了,呵呵。不过还是值得研究一下
rep movsd和loop是两码事，rep movsd后就直接交给cpu去完成了,
而loop每次完毕cpu都要和操作系统再打交道
rep movsd和loop是两条不一样的机器指令.
如果循环十次的话,用loop cpu需要十个机器指令,需要的时间就是
执行一个loop的时钟计数*10
用rep movsd的话就是一个机器指令,需要的时间是rep movsd的机器指令时间
当然执行这种复杂的指令rep movsd一次的cpu时钟触发可能比loop长.
汇编最终会转化为机器指令的，呵呵。一条机器指令用一系列的逻辑电路去实现
，我个人觉得拷贝内存和页大小是有关系的。我隐约记得以前学操作系统原理的时候有这个印象.
欢迎继续探讨

lijun4183: >>当然执行这种复杂的指令rep movsd一次的cpu时钟触发可能比loop长.
没错rep movsd一次的cpu时钟触发比loop长，关键是如果定长，不管多长，我们都可
看作O(1)。但是rep movsd的时钟长度是N相关的，所以rep movsd并非你认为的是一条
指令，即是定长的时间。所以说rep movsd的时间复杂度为O。
顺便说一句，这个在计算机原理的课程中讲的更清楚些。

lijun4183： 这个讨论跑题了。我想不必在讨论计算机的电路了吧。

跑得离谱了，回到正题。我认为，完全符合要求的算法可能不存在。