#### Splay时间复杂度证明

###### 证明.

$2\lg(x)-\lg(y)-\lg(z)$
$=\lg((y+z+1)^2)-\lg(y)-\lg(z)$
$=\lg(\frac{(y+z+1)^2}{yz})$
$=\lg(\frac{2yz}{yz}+\frac{y^2+z^2+1+2y+2z}{yz})$
$\geq \lg(2+\frac{y}{z}+\frac{z}{y})$
$\geq \lg(2+2)$
$=2$

###### 证明.

$r'(x)+r'(y)+r'(z)-r(x)-r(y)-r(z)$
$=r'(y)+r'(z)-r(x)-r(y)$
$\leq r'(x)+r'(z)-2r(x)$ 由于$size'(x)=size(x)+size'(z)+1$,根据定理0,加上2r'(x)-r'(z)-r(x)-2。
$\leq 3(r'(x)+r(x))-2$

$r'(x)+r'(y)+r'(z)-r(x)-r(y)-r(z)$
$=r'(y)+r'(z)-r(x)-r(y)$
$\leq r'(y)+r'(z)-2r(x)$,由于size'(x)=size'(y)+size'(z)+1,根据定理0,加上2r'(x)-r'(y)-r'(z)-2
$\leq 2(r'(x)-r(x))-2$

### 2条评论

1. 1楼

Thanks for all your valuable hard work on this site. Gloria enjoys conducting investigations and it’s obvious why. My spouse and i know all about the powerful tactic you render practical guides via the blog and as well as boost contribution from people on this topic and my child is without question discovering a lot. Take advantage of the remaining portion of the new year. You have been carrying out a stunning job.

2. I needed to create you the very little note to say thanks a lot as before regarding the magnificent techniques you’ve shown in this article. This has been certainly seriously open-handed of people like you to deliver easily all a number of us would have sold for an electronic book to make some bucks on their own, mostly considering that you could have tried it in case you wanted. These advice additionally worked as a great way to comprehend other people have the identical dreams much like mine to know the truth whole lot more with regard to this matter. I know there are millions of more enjoyable sessions ahead for people who start reading your website.