面试－C语言编程 - 第2页

tiezi · May 18th, 2005, 23:43

引用:

作者: 一路走过来

是merge sort吧，5(lg5)

你的算法比冒泡更进了一步,但是还不对,给个具体数字,哥们.

may1107 · May 18th, 2005, 23:52

引用:

作者: tiezi

真正的高手是研究算法的,既然大家讨论的这么热烈,我就出个当时上学时的作业给大家玩玩, 5个数排序最少要循环多少次?冒泡排序大家都知道吧,是N的平方,25次,还有更少的吗?

如果是用双指针，好象遍历一次就搞定了。

似是故人来 · May 19th, 2005, 00:13

似乎研究算法复杂度的提法一般都用O(f(n))和o(f(n))，多少次的说法比较少见吧？

一路走过来 · May 19th, 2005, 00:43

引用:

作者: 似是故人来

似乎研究算法复杂度的提法一般都用O(f(n))和o(f(n))，多少次的说法比较少见吧？

我也这仫认为。

我给的是worst case, BIG O.

tiezi 要的是最少.

关注中。

Viking · May 19th, 2005, 20:08

循环多少次的说法有问题。循环次数并不与复杂性有关。在这个问题上，比较的次数才是关键。如果不计较比较的次数，一次循环就可以搞定。
一般来说，如果只有固定数量的书需要排序，可以认为开销是常数时间，一般忽略不计。
MergeSort 的问题在于开销过大。QuickSort比较好。

此问题比较无聊。

UofTer · May 21st, 2005, 21:20

从头看到尾，的确是没有多少人还在用这个垃圾！

雇主也有毛病，老是把这块裹脚布在求职者中荡来荡去。郁闷！

beastmaster · May 21st, 2005, 21:49

引用:

作者: UofTer

从头看到尾，的确是没有多少人还在用这个垃圾！

雇主也有毛病，老是把这块裹脚布在求职者中荡来荡去。郁闷！

C/C++是COMPUTER SCIENCE 学生的基本修养. 不精通, 如何能理解系统. 特别是对性能和硬件要求高的系统或应用程序不用C/C++还不行.这就是REAL-TIME 和EMBEDDED编程大部分只用C/C++的原因.
你找不到这方面的工作或这方面的工作不多, 并不表示它就是垃圾. 由于会C/C++的人很多, 精通的人也不少, 当然竞争也很激烈, 现在不是高手很难入行. 特例除外.
你如果是学计算机的就别老说C是垃圾等, 这样会被人笑的.

tiezi · May 21st, 2005, 21:51

引用:

作者: Viking

循环多少次的说法有问题。循环次数并不与复杂性有关。在这个问题上，比较的次数才是关键。如果不计较比较的次数，一次循环就可以搞定。
一般来说，如果只有固定数量的书需要排序，可以认为开销是常数时间，一般忽略不计。
MergeSort 的问题在于开销过大。QuickSort比较好。

此问题比较无聊。

确切的说是比较的次数,5个数最少比较多少次能排出顺序?你能给出MergeSort和QuickSort的答案吗?

beastmaster · May 21st, 2005, 22:25

引用:

作者: tiezi

确切的说是比较的次数,5个数最少比较多少次能排出顺序?你能给出MergeSort和QuickSort的答案吗?

SORT 算法无非是用空间换取时间. 时间和空间都很优秀的是QUICK SORT, HEAP SORT.
RADIX SORT 最快, 但空间开销大, 还有如果从实际应用角度考虑, 数据少于10000, 用哪个SORTING 算法都差不多.
以下连接有图很形象.
http://tanksoftware.com/tutes/uni/sorting.html

tiezi · May 21st, 2005, 23:08

引用:

作者: beastmaster

SORT 算法无非是用空间换取时间. 时间和空间都很优秀的是QUICK SORT, HEAP SORT.
RADIX SORT 最快, 但空间开销大, 还有如果从实际应用角度考虑, 数据少于10000, 用哪个SORTING 算法都差不多.
以下连接有图很形象.
http://tanksoftware.com/tutes/uni/sorting.html

现在硬件很发达,空间已经不再是问题,所以时间最重要,处理同一个问题通常只考虑最快的算法,就象GOOGLE,据说它有上万台服务器,但它的搜寻速度是最快的,以空间换时间是显而易见的.我出的那个题只是想让大家玩玩,用手就能推算出来,不用什么公式一类的算法.另外你上面给的那个连接图里的i好象不是比较次数,只是外循环次数.

Viking · May 22nd, 2005, 10:11

C/C++ 和Java/C#有着几乎完全不同的应用领域。在底层开发环境里面, 硬件资源十分有限, C和汇编比较适合。另外，C语言比较适合的一个地方是编写操作系统，如你提到的RTOS。
在分布式网络应用上，C语言对系统架构的描述能力是远远比不上Java的。一般在这种情况下也很少用C。C语言不能说是垃圾，但在适用的领域里也远远谈不上唯我独尊。C的问题是可移植性不好，在这一点上，同样用于底层开发的J2ME就比C要好。C++总的来说不是很好的OO语言，设计得太复杂，完全没有必要（这是MS的观点，MS认为只能用C#来和Java抗衡）。
排序算法并不是用空间换时间。QuickSort就是可以sort in place。
内存空间的消耗同样很重要，特别在服务器端。你只要稍微想象一下，也许一台动态内容服务器要同时响应数千次的查询，每次查询都要排序上万个数，在这种情况下算法是非常重要的。而且这种情况非常常见。
另外，MergeSort和QuickSort通常是用递归算法（MergeSort也有sequential的算法），堆栈开销是不是也得算上呢？

一些常识而已。我看这里许多人都不是科班出身的吧？No offense, 随便说说。

May 19th, 2005, 00:13	只看该作者 #23
似是故人来 Junior Member 注册日期: Jul 2004 帖子: 607 声望: 206181	似乎研究算法复杂度的提法一般都用O(f(n))和o(f(n))，多少次的说法比较少见吧？
似是故人来 Junior Member 注册日期: Jul 2004 帖子: 607 声望: 206181

May 19th, 2005, 20:08	只看该作者 #25
Viking Senior Member 注册日期: Jul 2004 帖子: 212 声望: 3788	循环多少次的说法有问题。循环次数并不与复杂性有关。在这个问题上，比较的次数才是关键。如果不计较比较的次数，一次循环就可以搞定。一般来说，如果只有固定数量的书需要排序，可以认为开销是常数时间，一般忽略不计。 MergeSort 的问题在于开销过大。QuickSort比较好。此问题比较无聊。
Viking Senior Member 注册日期: Jul 2004 帖子: 212 声望: 3788

May 21st, 2005, 21:20	只看该作者 #26
UofTer Banned 注册日期: May 2005 帖子: 34 声望: 10	从头看到尾，的确是没有多少人还在用这个垃圾！雇主也有毛病，老是把这块裹脚布在求职者中荡来荡去。郁闷！
UofTer Banned 注册日期: May 2005 帖子: 34 声望: 10

May 22nd, 2005, 10:11	只看该作者 #31
Viking Senior Member 注册日期: Jul 2004 帖子: 212 声望: 3788	C/C++ 和Java/C#有着几乎完全不同的应用领域。在底层开发环境里面, 硬件资源十分有限, C和汇编比较适合。另外，C语言比较适合的一个地方是编写操作系统，如你提到的RTOS。在分布式网络应用上，C语言对系统架构的描述能力是远远比不上Java的。一般在这种情况下也很少用C。C语言不能说是垃圾，但在适用的领域里也远远谈不上唯我独尊。C的问题是可移植性不好，在这一点上，同样用于底层开发的J2ME就比C要好。C++总的来说不是很好的OO语言，设计得太复杂，完全没有必要（这是MS的观点，MS认为只能用C#来和Java抗衡）。排序算法并不是用空间换时间。QuickSort就是可以sort in place。内存空间的消耗同样很重要，特别在服务器端。你只要稍微想象一下，也许一台动态内容服务器要同时响应数千次的查询，每次查询都要排序上万个数，在这种情况下算法是非常重要的。而且这种情况非常常见。另外，MergeSort和QuickSort通常是用递归算法（MergeSort也有sequential的算法），堆栈开销是不是也得算上呢？一些常识而已。我看这里许多人都不是科班出身的吧？No offense, 随便说说。
Viking Senior Member 注册日期: Jul 2004 帖子: 212 声望: 3788