Question

几个数学证明题

1：

证明上面那个等式【X】，是向下取整函数 比如说[3.3]=3
对于向下取整函数 [x]=n ----> n<= x <n+1

2:

这是对O(g)的定义

3：证明

O(n）还是上面那个O

谢谢~





Answer 1

(1) x>0 则由x-[x]>=1/2 得 [x]+1/2<=x<[x]+1
2[x]+1<=2x<2[x]+2
所以[2x]=2[x]+1
x<0 同理可得(其中[x]-1<x<=[x]-1/2 )
(2)f(n)=n^2+n
g(n)=n^2
按定义 要有f(n)<=cg(n)
即 n^2+n<=c*n^2
n^2(c-1) -n=n(n(c-1)-1) >=0 可以得到c是存在的 这时只要n0(c-1)-1>=0 n0=[1/(c-1)]+1 (c>1)
那么只要n>n0 就可以有n^2+n<=c*n^2 总成立 。所以结论得证
（3）可以用假设法 ，f(n)=n^2 g(n)=n
假设存在c是正实数 存在n0是自然数 只要n>n0时 f(n)<=c*g(n)
这时n^2<=c*n
n(n-c)<=0 所以n-c<=0 n<=c
这与n>n0 总有f(n)<=c*g(n)是成立的是冲突的 （只要设n0>c）
所以结论得证

追问

2 3题的f(n)= xx g(n)=xx 是怎么得出来的啊？
谢谢

追答

So we define O(g) by f is in O(g) if ∃c∈R+ ∃n0∈N ∀n∈N n>=n0 ->f(n)=n0 有f(n)<=cg(n) 则 函数f 属于O(g)
所以这里的f(n)就是n^2+n O(n^2) 的 g(n)就是n^2 O(n)的g(n)=n

追问

n^2(c-1) -n=n(n(c-1)-1) >=0 可以得到c是存在的 请问这里是怎么的出来c是存在的啊？谢谢

追答

n是自然数 n(n(c-1)-1)>=0 可得 n(c-1)-1>=0
只要n(c-1)>=1
对于上式c是存在的 只要c>1 总有一个n>n0 使得n(c-1)>=1是成立的。

Answer 2

第一题：
因为x-[x]>=1/2，所以可以设x=[x]+a，其中a在1/2和1之间
那么[2x]=2[x]+[2a]，因为2a在1和2之间，所以[2a]=1
即[2x]=2[x]+1。后面2题看不懂，不好意思。

Answer 3

9:12:14
多少分

Answer 4

还是自己想的好！

Answer 5

Answer 6

追问

出门看车哈