数学符号问题 - 编程论坛

#2

莫云今次2009-08-18 00:21

不等

#3

Lambert0082009-08-18 10:36

相等啊，左右都是1+2+……+n+n

#4

XIAO荣2009-08-18 10:48

左边：(n-0)+(n-1)+……+(n-n-1)+n=n*n/2-n/2
右边: (1+n)+(2+n)+……+(n+n)=n/2+n*n
应该不等吧，不知道这样算对不对。

#5

ly8610142009-08-18 13:16

回复楼主 mfkblue

同意三楼，应该是那样的，在我们数学里面是这么算的，其实等号左边最外面那个括号可以去掉

#6

王晓明2009-08-18 14:21

同意三楼的

#7

mfkblue2009-08-18 15:44

目前比分3:2，认为相等的暂时领先.还是比较有争议的。

#8

pangding2009-08-18 16:29

回复 7楼 mfkblue

我觉得也是相等的。

Σ只管它后面的一项，除非加括号。
所以这个式子应该是 Σ(n-i) + n = Σj + n ，其中n应该看作是个常数。所以只要看 Σ(n-i) 和 Σj 是不是相等就行了，显然是相等的。

#9

mfkblue2009-08-18 22:25

这样子理解对不对?
左边看成:
int s=0;
for(int i=0;i<=n-1;i++)
s=s+(n-i);

右边看成:
s=0;
for(int j=1;j<=n;j++)
s=s+j;

[ 本帖最后由 mfkblue 于 2009-8-18 22:29 编辑 ]

#10

ly8610142009-08-18 22:39

回复 9楼 mfkblue

这样子理解没错，但你把它复杂化了，这个问题完全没有争议，除非某本书上有他自定义的西格玛号，如果有，也是违背了常规定义，这个式子左右是相等的，
左边 = n + ... + 3 + 2 + 1 + n
右边 = 1 + 2 + 3 + ... + n + n

#11

mfkblue2009-08-18 23:34

如我那样理解没错下次碰到我还是会这样子花开的，我觉得是简单化了，

数据结构里这章的问题我前几天看书直接跳过了，书看到后面，经常蹦出大O小o之类符号表示函数的复杂度，看不懂所以这两天又重新看这一章，不过今天又看了一天，还是决定跳过，太难懂了.
主要认为好像没什么用,我会写的话，代码自然会简单，高效，不会写的复杂度再高也没办法。

#12

ly8610142009-08-18 23:58

回复 11楼 mfkblue

我说的复杂化是说的单从判断这个数学式子有没有错误上，只从纯数学方面就可以知道这个式子没错。
当然，你写的代码也说明你已经理解这个数学式子了。
复杂度能够衡量一个算法的效率，在算法分析中肯定要用到的，建议楼主要看好这一部分，你可以看一下《算法导论》中第三章讲的，大O是渐进上界，小o是渐进上确界，关于上界、上确界，你可以看一下大学高等数学或者是数学分析，简单的说，如果有上界的话，上界有无穷多个，而上确界只有一个，上确界就是最小的上界。

#13

遥天2009-08-19 14:14

左边=(n-0)+(n-1)+(n-2)+……+[n-(n-1)]+n
      =n*[(n-1)+1]-[0+1+2+3+...+(n-1)]+n
      =n*n-[1+(n-1)]*(n-1)]/2+n
      =n^2-n*(n-1)/2+n
      =(n^2+3n)/2

右边=1+2+3+...+n+n
    =(1+n)*n/2+n
    =(n^2+3n)/2
当然左边等于右边

#14

sherwin2009-08-19 21:53

毫无疑问，相等的。前边是从n加到1；后边是1加到n;剩下的两边的两个n可以消掉

#15

pangding2009-08-19 22:47

回复 12楼 ly861014

其实这个和确界还是有点区别的。如果学过数分的话，会发现它和无穷大量和无穷小量的阶有点像。其实就是那个，连用的符号都一样~ 那个O，就是阶(Order) 的首字母。

我觉得学编程，如果不是特别明白的话，不用在大O 的严格数学定义上下太大功夫。其实所谓复杂度，应该多少自己凭感觉能感觉出来，不是代码越简单时间复杂度越低(当然代码简单应该也是某种复杂度低的表现，只不过我不知道那叫什么复杂度了~

)，而是干的事越少越好。

#16

ly8610142009-08-19 23:01

回复 15楼 pangding

g(x)的所有无穷小量所组成的集合就是这里的小o(g(x))，其无穷大量所组成的集合是小w(g(x))(欧米伽)。

我在12楼说错了，小o不是渐近上确界，是渐近上界集去掉渐近上确界所得的集合。

#17

mfkblue2009-08-19 23:23

回复 15楼 pangding

同意，即使我知道代码复杂度高，我写不出简单高效的代码，那也没办法。
数据结构我跳过了三章了。
程序性能，看不懂跳过.
模拟指针，有指针要模拟指针干什么,太麻烦跳过.
矩阵,不就是两维数组，搞这么麻烦干什么.跳过.