takeda25 https://blog.hatena.ne.jp/takeda25/ アスペ日記 https://takeda25.hatenablog.jp/ 「区間[0,M)なるN個の一様乱数を昇順に配列に格納したい．M は十分に大きい．領域計算量O(N)，時間計算量O(N)でこれを行う方法を考えよ．」という問題について、バケットソートを使って Python で書いてみた。比較回数（適当だから間違ってるかも）は、1000個でやるとだいたい600〜700回になる。バケットのソートには、Wikipediaの挿入ソートを使った。 import random, math M = 2 ** 32 N = 1000 def insertion_sort(target_list): steps = 0 for i in range(1, len(target_l… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftakeda25.hatenablog.jp%2Fentry%2F20100627%2F1277629883" title="一様乱数のソート - アスペ日記" 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 2010-06-27 18:11:23 rich https://takeda25.hatenablog.jp/entry/20100627/1277629883 1.0 100%