Question

一个数学证明题

1:
证明上面那个等式【X】，是向下取整函数 比如说[3.3]=3

2:

这是对O(g)的定义

3：证明O(n）还是上面那个O

谢谢~
补充第一题：对于向下取整函数 [x]=n ----> n<= x <=n+1





Answer 1

1、设x=△+[x]，则有1＞△≥1/2。[2x]=[2([x]+△)]=[2[x]+△]=2[x]+[2△]，
因为2＞2△≥1，所以[2三角形]=1，所以有[2x]=2[x]+1。得证。
2、如果存在一个正实数c和一个自然数n0，满足对于任意大于n0的自然数n，有f(n)≤cg(n)，则称f是属于O(g)的。
取c=2，n0=1，则有对于任意自然数n＞1，有n^2+n≤2(n^2)，因为满足定义，所以得证。
3、假设存在一个实数c和一个自然数n0，满足对于任意大于n0的自然数n，有f(n)≤cg(n)。
令n^2＞cn，解得n＜0或n＞c。所以可得当n＞max{n0，c}的时候，f(n)≤cg(n)不成立，与假设矛盾。所以假设不成立，所以n^2不属于O(n)。

大概思路就是这样，但是步骤可能不是很标准。

你的补充应该是有点问题吧，对于向下取整函数 [x]=n ----> n<= x <n+1

另外这是算法分析与设计课上的练习吗？