w ͠લͬͯ ΛਪఆͰ͖ΔͳΒɺͦͷࣄલࣝʹΑͬͯ ͲͷఔΫΤϦॲཧΛ͘Ͱ͖Δ͔ʁ w ˠಈతࢬמΓΞϧΰϦζϜͷ͕Ҏ্վળ͢Δ͜ͱΛࣔͨ͠ w 32 w ͷࣄલࣝΛͬͯ.BY4DPSFɺ8"/%ɺ#.8ͷΑ͏ͳख๏ΛվྑͰ͖Δ͔ʁ w ˠͯ͢ͷख๏ͰΞϧΰϦζϜతͳվળ͕ՄೳͰ͋Δ͜ͱΛࣔͨ͠ Θk (D, Q) Θk (D, Q) Θk (D, Q)
࣌ؒܭࢉྔվળͤͣ࠷ѱέʔεͰ w 5PQL015 w UPQLͷϦετΛٻΊɺͦΕΛ͞Βʹ015ͰϑΟϧλ͢Δ w LݸະຬͷϦετʹ͢Δ͜ͱͰϝτϦοΫΛ࠷େԽͰ͖Δ͜ͱ͋ΔͨΊ w PQUJNBMʢۙࣅʹΑΔΤϥʔ͕ʣͰ͋Δ͜ͱ͕ূ໌Ͱ͖Δ w ࣌ؒܭࢉྔ࠷ѱͰ Θ(nk) Θ(n log k + k2)