アルゴリズムの複雑さ：パラメータとして「消費電力」を見分ける方法は？

Question

アルゴリズムの複雑さを分析するためのバロメーターとみなされます。しかし、モバイル機器にGPUが搭載されている今日では、モバイルデバイス上で複雑なアルゴリズムを実行するためにその高性能を使用できる数多くのアプリケーションがあります。たとえば、iOSのメタルフレームワークをGPGPU操作に使用できます。しかし、言うまでもなく、それは多くの力を消費する。だから私の質問は、私が開発/実装している、たとえば、モバイルデバイス上のグラフ検索アルゴリズムで、私はまた、時空とともに、私のアルゴリズムの "パワー"の複雑さを考慮してはいけないということですか？今、私は議論が、アルゴリズムが直接消費しないパワーであり、それに完全に同意するということができるということを知っています。だから、私の文法は、アルゴリズムの効率を測定するもう一つの次元であると言っても間違いです。しかし、アルゴリズムの性能指標として見えるべきではありませんか？

Answer 1

これを可能にするには、アルゴリズムのアトミック操作に関連するエネルギー消費モデルが必要です。

「複数のエネルギーを消費します」、「メモリスロットは単位時間あたり2つのエネルギーを消費します」などのように多分、Energy = Time x Spaceという関係が理にかなっているかもしれません。

とにかく、このような「ナイーブな」モデルは、時間の複雑さのモデルと同じ現象に悩まされる可能性があります。現代のアーキテクチャーの動作とはまったく似ておらず、桁違いに間違っている可能性があります。

より正確なモデルを使用すると、解析的に扱いにくいものになります。

Answer 2

No. 複雑さは、アルゴリズムが時間/メモリでどのように比例するかを説明します。パワーは時間とメモリの関数になります。

アルゴリズムA - O（N^2）とB - O（N^3）があり、両方とも同じ問題を解決したとします。 n = 1000の場合、Bは1単位の電力を使用しますが、Aは20を使用します。今度は、n = 10kまで拡張するとBには1000単位の電力が必要ですが、Aには2000のみが必要です。n = 100kでBは、 Aは200,000を必要とします。等々。 これは、エネルギー消費がアルゴリズムの実行に対して一定であることを前提としています。

ところで、同じことが時間とともに起こります。たとえば、短い配列の場合、線形検索に勝るものはありません。

特定のケース（固定解像度のUIをレンダリングする）では、消費電力を測定して最適化することが理にかなっています。しかし、今日の決議のために働くのは、必ずしも明日には正しいことではありません。