smoking186 https://blog.hatena.ne.jp/smoking186/ 186 @ hatenablog https://186.hatenablog.com/ study 1+2+...+n = O(n) となることをいまから証明しますが，もちろんこれは間違っています． (真実は 1+2+...+n = n(n+1)/2 なので．) どこがまちがっているでしょう？というのがクイズです． 証明 nに関する数学的帰納法． n=1のとき，左辺は1で右辺はO(1)．1=O(1)なので成立． n>1のときを考えると，1+2+...+n=(1+2+...+(n-1))+n = O(n-1)+n = O(n)+n = O(n)． ここで，「1+2+...+(n-1)=O(n-1)」という帰納法の仮定を用いた． 証明終 このクイズはいろいろ示唆に富んでると思うのです．考えてみて… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20071012%2F1192195267" title=" オーダー記法の問題 - 186 @ hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2007-10-12 22:21:07 rich https://186.hatenablog.com/entry/20071012/1192195267 1.0 100%