我覺得我解釋不清楚

下麵是源程序（編譯通過）。有3個變量；我認為是O(n)的

------------------------------------
using System;
using System.Collections.Generic;
using System.Text;

namespace netiq
{
class Program
{
const int n = 10;

static int f(int k)
{
return (k % 2 > 0) ? ((k - 1) / 2 + n) : k / 2;
}
static int g(int k)
{
return (k }
static string toString(int[] a)
{
string str = a[0].ToString();
for (int i = 1; i {
str += " " + a[i];
}
return str;
}

static void Main(string[] args)
{
string str;
int[] a = new int[n * 2];
for (int i = 0; i
for (int k = 0; k Console.WriteLine(toString(a));

// run algorithm
for (int k = 0; k {
if (g(k) == a[k]) { continue; }
int i = k, j;
while (f(i) != k)
{
j = a[f(i)];
a[f(i)] = i;
i = j;
}
a[k] = i;
}

Console.WriteLine(toString(a));
return;
}
}
}

所有跟帖： 

• 主要是難以判斷一個位置有沒有排好。 -亂彈- ♂ (355 bytes) () 07/30/2009 postreply 17:30:25

• 你可以run一下這個程序，對任何n都適用 -說了就走- ♂ (357 bytes) () 07/30/2009 postreply 20:47:50

• 你一直在假設a[k]=k。沒有這個假設你的算法不成立 -康MM- ♀ (0 bytes) () 07/31/2009 postreply 07:14:51

• 那麽請問你的假設是什麽？ -說了就走- ♂ (216 bytes) () 07/31/2009 postreply 18:16:46

• 還是問冬瓜太郎吧，他說可以就可以 -康MM- ♀ (177 bytes) () 08/02/2009 postreply 10:25:52

• 你說得很有道理 -說了就走- ♂ (2675 bytes) () 08/02/2009 postreply 13:50:02

• 我還是覺得我們在說兩件不同的事 -康MM- ♀ (0 bytes) () 08/06/2009 postreply 17:49:24