computer 版 (精华区)

发信人: remember (Learning C++), 信区: program
标  题: Re: 找第n个最小数
发信站: 听涛站 (2001年10月15日21:45:24 星期一), 站内信件

  hehe....其实这个问题是有现成答案的，我自己想不出O(n)的算法
  本来标准答案早该贴出来了，可是老板的课的作业很是让我faint，
  这周内吧，我把书上的答案贴出来给大家看看～～～
  至于时间复杂度按什么计算，我觉得自然是最终的汇编指令数了
  大概就认为是时钟周期吧，不过我觉得这个不是特别重要，
  O(n)和O(nlogn)和O(n^2)我们总能分辨吧，呵呵

【 在 gutentag ( Bonjour && deeply in LOVE on the web ) 的大作中提到: 】
: 首先应该明确一下，到底应该用什么来讨论，
: 是“交换次数”还是“比较次数”。
: 我以为习惯上用的是“交换次数”，仔细想一想
: 也不能肯定前者就一定占据主导地位。如果有时
: 间查查硬件的书，算算时钟周期更能说明问题。
: 【 在 remember (Learning C++) 的大作中提到: 】
: :  ok....可以看到，这个程序在最坏情况下是O(n^2)，
: :  平均时间应该是O(n)，对否？
: :  要是要求最坏情况下是O(n)呢？
: :  btw: 你的签名档、昵称弄的我每次都觉得看不见部分东西（我用的是Sterm）
: .................（以下省略）

--
    洛阳亲友如相问  一片冰心在玉壶
※ 来源:·听涛站 tingtao.dhs.org·[FROM: 匿名天使的家]