- [[簡潔データ構造]]のサイズの上界(Upper-bound)を求める際に用いられる - [#空間計算量](空間計算量) [[凸関数]]の定義 ![[assets/66372abde2e5450023328316.png]] - 任意の$x_1, x_2 \in I$と$0 \le \lambda \le 1$について、以下の不等式を満たすとき$f$を下に凸関数と呼ぶ - $f(\lambda x_1 + (1-\lambda) x_2) \le \lambda f(x_1) + (1-\lambda)f(x_2)$ - $x_1 \le \lambda x_1 + (1-\lambda)x_2 \le x_2$、$f(x_1) \le \lambda f(x_1) + (1-\lambda)f(x_2) \le f(x_2)$であることに注意 - 狭義凸関数の定義: 任意の$x_1, x_2 \in I (x_1 \ne x_2)$と$0 \lt \lambda \lt 1$について以下の不等式を満たすとき$f$を下に狭義凸関数と呼ぶ - $f(\lambda x_1 + (1-\lambda)x_2) \lt \lambda f(x_1) + (1-\lambda)f(x_2)$ - 例: $x^2, logx, e^x...$ - $f(x)$が定義されているところに、フラットなところ、直線的なところがなにもないイメージ イェンセンの不等式 - 凸関数の定義の一般化 - $f(x)$が下に凸の関数で、$x_1, x_2, ..., x_n \in I, \lambda_1, ..., \lambda_n$を$\sum_{k=1}^{n}{\lambda_k=1}$かつ$\lambda_k \ge 0$とする。このとき、次のような不等式が成り立つ。 - $\sum_{k=1}^{n}\lambda_{k}f(x_k) \geq f( \sum_{k=1}^{n} \lambda_{k}x_k)$