Algorithm 版 (精华区)

发信人: ssos (存在与虚无·守拙), 信区: Algorithm
标  题: [合集]sino讲一下你做的755好嘛
发信站: 哈工大紫丁香 (2002年08月13日08:20:48 星期二), 站内信件


────────────────────────────────────────
 pamws (书虫)                         于 2002年08月05日15:18:21 星期一 说道:

刚刚看过你的个人文集, 那个memcmp不大懂, 我自己写的程序会超时.
thanks!

────────────────────────────────────────
 sino (仿佛永远分离,却又终身相依)     于 2002年08月05日16:28:52 星期一 说道:

就是一个排序吧... 
memcmp 和 strcmp 很像
【 在 pamws (书虫) 的大作中提到: 】
: 刚刚看过你的个人文集, 那个memcmp不大懂, 我自己写的程序会超时.
: thanks!

────────────────────────────────────────
 pamws (书虫)                         于 2002年08月05日22:46:46 星期一 说道:

我是在读入的同时作插入排序的, 用类似vector的链表类, 复杂度应该是O(n^2), 不知
道为什么会超时.
【 在 sino (仿佛永远分离,却又终身相依) 的大作中提到: 】
: 就是一个排序吧... 
: memcmp 和 strcmp 很像
: 【 在 pamws (书虫) 的大作中提到: 】
: : 刚刚看过你的个人文集, 那个memcmp不大懂, 我自己写的程序会超时.
: : thanks!

────────────────────────────────────────
 GREnTOFEL (厉兵秣马)                 于 2002年08月06日10:41:06 星期二 说道:

sino用的是快速排序法，复杂度是nlog2n（如果我没有记错的话）
这样当n=100,000时，快速排序最好的情况是100,000*log2100,000=1,660,964
而插入排序实际为1/2*n^2,则=5,000,000,000
【 在 pamws (书虫) 的大作中提到: 】
: 我是在读入的同时作插入排序的, 用类似vector的链表类, 复杂度应该是O(n^2), 不知
: 道为什么会超时.
: 【 在 sino (仿佛永远分离,却又终身相依) 的大作中提到: 】
: : 就是一个排序吧... 
: : memcmp 和 strcmp 很像

────────────────────────────────────────
 cucme (说你说我)                     于 2002年08月06日12:35:24 星期二 说道:

【 在 GREnTOFEL (厉兵秣马) 的大作中提到: 】
: sino用的是快速排序法，复杂度是nlog2n（如果我没有记错的话）
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                        你记错了。qs的平均时间复杂度是nlog2n, 
                        但是最差时间杂度和插入冒泡等等没有本质区别。
: 这样当n=100,000时，快速排序最好的情况是100,000*log2100,000=1,660,964
: 而插入排序实际为1/2*n^2,则=5,000,000,000
: 【 在 pamws (书虫) 的大作中提到: 】
: : 我是在读入的同时作插入排序的, 用类似vector的链表类, 复杂度应该是O(n^2), 不知
: : 道为什么会超时.

────────────────────────────────────────
 pamws (书虫)                         于 2002年08月06日13:07:16 星期二 说道:

等我回寝室把程序贴出来, 请大家帮忙检查吧!
【 在 cucme (说你说我) 的大作中提到: 】
: 【 在 GREnTOFEL (厉兵秣马) 的大作中提到: 】
: : sino用的是快速排序法，复杂度是nlog2n（如果我没有记错的话）
:                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
:                         你记错了。qs的平均时间复杂度是nlog2n, 
:                         但是最差时间杂度和插入冒泡等等没有本质区别。
: : 这样当n=100,000时，快速排序最好的情况是100,000*log2100,000=1,660,964
: : 而插入排序实际为1/2*n^2,则=5,000,000,000

────────────────────────────────────────
 Lerry (想不开·撞树)                 于 2002年08月06日21:08:43 星期二 说道:

怎么还没有贴
【 在 pamws (书虫) 的大作中提到: 】
: 等我回寝室把程序贴出来, 请大家帮忙检查吧!
: 【 在 cucme (说你说我) 的大作中提到: 】
: :                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
: :                         你记错了。qs的平均时间复杂度是nlog2n, 
: :                         但是最差时间杂度和插入冒泡等等没有本质区别。

────────────────────────────────────────