

離散ウェーブレット変換の計算量はO(N)で、高速フーリエ変換の場合はO(N log N)になるそうですが

離散ウェーブレット変換の式も Σ(シグマ記号:summation)が２つのため二重ループになり  
O(N^2)になると思うのですが、なぜ、O(N)になるのですか？


CC BY-SA 3.0
2015-02-21T17:32:04.813
6880
2015-02-22T12:38:45.430
2015-02-22T12:38:45.430
7978
question
アルゴリズム 計算量
ウェーブレット変換とフーリエ変換の計算量