亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

  免費(fèi)注冊(cè) 查看新帖 |

Chinaunix

  平臺(tái) 論壇 博客 文庫(kù)
1234下一頁(yè)
最近訪問(wèn)板塊 發(fā)新帖
樓主: emacsnw
打印 上一主題 下一主題

[算法] 剛看到的一個(gè)排序算法題,大家討論討論。 [復(fù)制鏈接]

論壇徽章:
0
11 [報(bào)告]
發(fā)表于 2006-12-28 22:48 |只看該作者
原帖由 bleem1998 于 2006-12-28 20:52 發(fā)表
能否照顧一下我這個(gè)數(shù)據(jù)結(jié)構(gòu)盲
請(qǐng)說(shuō)明一下什么是"O(1)的輔助空間"
3Q

指需要的輔助空間為常數(shù)大小(在算法確定時(shí)就確定了,不會(huì)隨著問(wèn)題規(guī)模改變而改變,跟時(shí)間復(fù)雜度類似)

論壇徽章:
0
12 [報(bào)告]
發(fā)表于 2006-12-28 22:49 |只看該作者
原帖由 bleem1998 于 2006-12-28 21:07 發(fā)表
我覺得這個(gè)題目是很有深意的
這個(gè)數(shù)組就像一個(gè)大公司
每個(gè)位置代表一個(gè)職位
那些重復(fù)的數(shù)字代表正在做著同樣重復(fù)工作的員工
現(xiàn)在要把這個(gè)大公司拆分成若干小公司
小公司里大家各司其職沒有重復(fù)
: )
發(fā)下 ...

想得不錯(cuò)

論壇徽章:
0
13 [報(bào)告]
發(fā)表于 2006-12-28 23:16 |只看該作者
原帖由 tyc611 于 2006-12-28 22:48 發(fā)表

指需要的輔助空間為常數(shù)大小(在算法確定時(shí)就確定了,不會(huì)隨著問(wèn)題規(guī)模改變而改變,跟時(shí)間復(fù)雜度類似)


受教了
但似乎不太夠啊
請(qǐng)問(wèn)網(wǎng)上有沒有什么資料是講這個(gè)的?
經(jīng)常看到有什么時(shí)間復(fù)雜度O(X)什么的
不明白是什么意思啊
我的數(shù)據(jù)結(jié)構(gòu)書上也沒解釋
這樣讓我感覺自己非常的土

論壇徽章:
0
14 [報(bào)告]
發(fā)表于 2006-12-29 11:18 |只看該作者
原帖由 bleem1998 于 2006-12-28 23:16 發(fā)表


受教了
但似乎不太夠啊
請(qǐng)問(wèn)網(wǎng)上有沒有什么資料是講這個(gè)的?
經(jīng)?吹接惺裁磿r(shí)間復(fù)雜度O(X)什么的
不明白是什么意思啊
我的數(shù)據(jù)結(jié)構(gòu)書上也沒解釋
這樣讓我感覺自己非常的土


通常算法分析的書籍一上來(lái)就講這個(gè),比如《算法導(dǎo)論》之類的書

論壇徽章:
0
15 [報(bào)告]
發(fā)表于 2006-12-29 11:37 |只看該作者
原帖由 tyc611 于 12/28/06 22:48 發(fā)表

指需要的輔助空間為常數(shù)大。ㄔ谒惴ù_定時(shí)就確定了,不會(huì)隨著問(wèn)題規(guī)模改變而改變,跟時(shí)間復(fù)雜度類似)


確切的說(shuō)這個(gè)也不對(duì)。。。
是存在一個(gè)常數(shù)上界。。。需要的空間不一定是常數(shù)

論壇徽章:
0
16 [報(bào)告]
發(fā)表于 2006-12-29 12:16 |只看該作者
原帖由 ArXoR 于 2006-12-29 11:37 發(fā)表


確切的說(shuō)這個(gè)也不對(duì)。。。
是存在一個(gè)常數(shù)上界。。。需要的空間不一定是常數(shù)

不是常數(shù)上界的,是不是算做O(n)?

論壇徽章:
0
17 [報(bào)告]
發(fā)表于 2006-12-29 12:29 |只看該作者
原帖由 namtso 于 12/29/06 12:16 發(fā)表

不是常數(shù)上界的,是不是算做O(n)。


不是...不是常數(shù)的函數(shù)多了去了...

論壇徽章:
0
18 [報(bào)告]
發(fā)表于 2006-12-29 12:42 |只看該作者
原帖由 emacsnw 于 12/28/06 16:33 發(fā)表
給你一個(gè)已經(jīng)排好序的數(shù)組a,里面可能有重復(fù)元素,比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5},F(xiàn)在需要重新調(diào)整a里面的元素為a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1},要求里面的每個(gè)子序列都是有序的,并且其中的元素唯 ...


如果數(shù)組是浮點(diǎn)數(shù), 但是題目保證輸入都是整數(shù)的話, 利用小數(shù)部分保存信息可以做到O(n)...
但是有點(diǎn)cheat了...

論壇徽章:
0
19 [報(bào)告]
發(fā)表于 2006-12-29 13:20 |只看該作者
想了一個(gè)算法
只需要一個(gè)交換變量就可以了
排序過(guò)程是這樣的

  1. 1, 1, 1, 2, 3, 3, 4, 5, 5
  2. 1, 2, 1, 1, 3, 3, 4, 5, 5
  3. 1, 2, 3, 1, 1, 3, 4, 5, 5
  4. 1, 2, 3, 4, 1, 3, 1, 5, 5
  5. 1, 2, 3, 4, 5, 3, 1, 1, 5
  6. 1, 2, 3, 4, 5, 1, 3, 1, 5
  7. 1, 2, 3, 4, 5, 1, 3, 5, 1
復(fù)制代碼


排序規(guī)則如下

  1. a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5};
  2. int part_ok = 0;
  3. for (i = 1; i < sizeof(a)/sizeof(a[0]); i++) {
  4.         //查找a[i-1]后面第一個(gè)比a[i-1]大的數(shù)
  5.         //如果遇到比a[i-1]小的數(shù),如果park_ok==1則交換那個(gè)數(shù)和a[i-1]的位置,park_ok=1,i--,continue
  6.         //如果找到比a[i-1]大的,則交換這個(gè)數(shù)和a[i]的位置,park_ok=0, continue
  7.         //如果找不到,park_ok=1,i++,continue    (這說(shuō)明其中一個(gè)小分公司已經(jīng)建好)

  8. }
復(fù)制代碼

[ 本帖最后由 bleem1998 于 2006-12-29 13:46 編輯 ]

論壇徽章:
0
20 [報(bào)告]
發(fā)表于 2006-12-29 13:31 |只看該作者
原帖由 bleem1998 于 2006-12-29 13:20 發(fā)表
想了一個(gè)算法
只需要一個(gè)交換變量就可以了
排序過(guò)程是這樣的
[code]
1, 1, 1, 2, 3, 3, 4, 5, 5
1, 2, 1, 1, 3, 3, 4, 5, 5
1, 2, 3, 1, 1, 3, 4, 5, 5
1, 2, 3, 4, 1, 3, 1, 5, 5
1, 2, 3, 4, 5, 3, 1,  ...

你這樣做,第一遍之后就把剩下的子序列打亂了,不知道你怎么處理剩下的
您需要登錄后才可以回帖 登錄 | 注冊(cè)

本版積分規(guī)則 發(fā)表回復(fù)

  

北京盛拓優(yōu)訊信息技術(shù)有限公司. 版權(quán)所有 京ICP備16024965號(hào)-6 北京市公安局海淀分局網(wǎng)監(jiān)中心備案編號(hào):11010802020122 niuxiaotong@pcpop.com 17352615567
未成年舉報(bào)專區(qū)
中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)會(huì)員  聯(lián)系我們:huangweiwei@itpub.net
感謝所有關(guān)心和支持過(guò)ChinaUnix的朋友們 轉(zhuǎn)載本站內(nèi)容請(qǐng)注明原作者名及出處

清除 Cookies - ChinaUnix - Archiver - WAP - TOP