第3章データ構造とアルゴリズム
TECHNOLOGY IN EVERYDAY LIFE日常生活の中の技術
Arranging Invisible Icons in Quadratic Time見えないアイコンを2次の時間で並べる
Have you ever been annoyed by computer slowness? For some users, opening the start menu can take 20 seconds because of an O(N2) algorithm, where N is the number of desktop files. The Microsoft Windows computer operating system allows users to organize files directly on top of their desktop wallpaper. A quadratic-time algorithm arranges these desktop icons in a grid layout so that they fill column-by-column starting from the left side of the screen. The algorithm is executed whenever the user opens the start menu or launches the file explorer.
英語のヒント
コンピューターの遅さにいらだったことはあるだろうか。利用者によっては、O(N2)のアルゴリズムのために、スタートメニューを開くのに20秒かかる。ここでNはデスクトップのファイル数である。Microsoft Windowsのオペレーティングシステムでは、デスクトップの壁紙の上にファイルを直接並べられる。2次の時間を要するアルゴリズムが、画面の左から1列ずつ埋まるように、デスクトップのアイコンを格子状に配置する。このアルゴリズムは、スタートメニューを開くたび、またはファイルエクスプローラーを起動するたびに実行される。
Most users only keep a couple dozen desktop icons, so the O(N2) algorithm takes microseconds—practically unnoticeable. But for users with hundreds of desktop icons, the impact of each additional icon adds up. With 1,000 desktop files, launching the start menu takes 20 seconds. With 10,000 desktop icons, the runtime grows to 30 minutes!
英語のヒント
大半の利用者がデスクトップに置くアイコンは2ダースほどなので、O(N2)のアルゴリズムはマイクロ秒で終わり、実質的には気付かない。しかし、何百個ものアイコンがある利用者では、1個追加するごとの影響が積み重なる。デスクトップのファイルが1,000個あると、スタートメニューを開くのに20秒かかる。10,000個のアイコンがあると、実行時間は30分にまで延びる。
To avoid the clutter of thousands of desktop icons, users can hide desktop icons. But this does not prevent the quadratic-time algorithm from running. Users with too many desktop icons beware: your computer slowness may be due to arranging invisible icons in quadratic time.3
英語のヒント
何千ものアイコンでデスクトップが散らかるのを避けるため、アイコンを非表示にすることはできる。しかし、それでも2次の時間を要するアルゴリズムの実行は止まらない。デスクトップに大量のアイコンを置く利用者は注意してほしい。コンピューターが遅いのは、見えないアイコンを2次の時間で並べているせいかもしれない。3