算法导论第三版的翻译…

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4320 天前的主题，其中的信息可能已经有所发展或是发生改变。

算法导论第三版
中文版p16 原书p29

习题 2.2-4
How can we modify almost any algorithm to have a good best-case running time?

机械工业出版社的简体中文翻译版作如下翻译：
我们可以如何修改几乎任意算法来使之具有良好的最好情况运行时间？

T-T 我觉得还是英文版容易懂…

算法

翻译

第三版

16 条回复 • 1970-01-01 08:00:00 +08:00

luin

2013-01-28 23:49:55 +08:00

翻译得毫无破绽哈哈

wa7chen

2013-01-28 23:51:03 +08:00

重量级的书还是直接E文来的好~~~

liuxurong

2013-01-29 00:07:32 +08:00

有枪吗？一枪打死翻译的。 ^-^

ini

2013-01-29 00:08:28 +08:00

一定是你的打开方式不对。。

dreampuf

2013-01-29 02:21:00 +08:00

我们怎样才能修改几乎所有的算法有一个良好的运行时间最好的情况吗？

from google translation
http://translate.google.cn/?hl=en#en/zh-CN/How%20can%20we%20modify%20almost%20any%20algorithm%20to%20have%20a%20good%20best-case%20running%20time%3F

dreampuf

2013-01-29 02:27:50 +08:00

不查不知道，长知识了。

http://weibo.com/1739612153/zgD1HxqIV

dndx

2013-01-29 02:34:34 +08:00

我们应如何修改使几乎任何算法都具有良好的最好运行时间？

wontoncc

2013-01-29 08:25:00 +08:00

这个翻译是词对词的 literal translation 了…

+ “几乎所有”、“几乎任意”这种译法出现在这个句子中并不太符合中文的习惯；一般地，窃以为该用“绝大部分”。
+ “良好的”、“最好的”这两个形容词让人昏头转向，从上下文明显可知“best-case running time”译为“最短运行时间”/“最速运行时间”等突出时间长度词语更恰当；另外对于前置的“good”，我认为是可以省译的，因为其含义已经包含于“best-case”当中（不“good”怎么称“best”呢？），译出反而有失简洁。如果想译出，窃以为应译为表现突出人对物感受的形容词，比如意译为“让人振奋的”之类。
+ 从句式来说，这句话用逐字对译其实是可取的，而且使伇动词的译法也很恰当（“使之…”）。

这里献丑给出一个译本：
我们该如何修改绝大部分算法使其具有最短运行时间呢？

JunkFood

2013-01-29 11:29:45 +08:00

@wontoncc 这个翻译是不准确的
best-case running time是指算法在理想情况下的运行时间，亦即算法运行时间的下限
而对应的worst-case running time 则是算法在最不理想的情况下的运行时间，亦即算法运行时间的上限
比如，如果在一个长度为n的数组中进行线性搜索，best-case running time 就是被搜索元素为数组第一个元素时的运行时，而worst-case running time则是被搜索元素为数组最后一个元素时的running time
对于某些算法，best-case running time和worst-case running time可能有很大的差距（在上例中一个是O(1)，而另一个是O(N)），单纯谈论最短运行时间并不总是能够保证两者同时取得最短运行时间。