「diffの動作原理を知る」の記事に出てくるアルゴリズムの名前について
「diffの動作原理を知る」の記事に出てくるO(ND)とO(NP)という言葉ですが、記事中ではこれら2つの言葉をアルゴリズムの名前として扱っています。そして、私はこれは計算量とアルゴリズムの名前の両方を表しているんだとずっと思っていました。
しかし、何人かの方から「O(ND)やO(NP)というのはあくまでアルゴリズムの計算量のことであって、アルゴリズムの名前ではないのではないか(もしくは、名前ではない)」というご指摘を頂きまして、私の方でも論文を読み直して確認しました。それで、注意して読み直してみると、このアルゴリズムの名前はO(ND)であるだとかO(NP)であるというようなことを書いている箇所は見あたりませんでした。「An O(NP) Sequence Comparison Algorithm」の論文は(冗談抜きで)数十回も読んだはずなのに、かなり根本的な部分でミスをしてしまった自分が情けないです。
アルゴリズムの名前ですが、論文中では明確に命名されていないので、アルゴリズムの論文の著者(first-author)の名前を取って以下のように表記するのがよいかと思います(サポートサイトにも掲載されました)。
誤 | 正 |
---|---|
O(ND) | MyersのO(ND)アルゴリズム |
O(NP) | WuのO(NP)アルゴリズム |
関係者や読者の方には度々ご迷惑をおかけして申し訳ありませんでした。以後、気を付けます。また、本件について貴重な意見を頂戴したm0h1canさん、id:smoking186さん(関連ページ)に感謝致します。