最简单的正确答案是 DFT 在$O(N_e^3)$. 这是因为您最终将一个哈密顿量对角化，其维度与选举次数成正比，并且对角化在技术上是$O(n^3)$.

实际上，DFT 是一堆步骤，不同的步骤在不同的上下文中是速率限制的。如果我们将自己局限于平面波 (PW) DFT（VASP、ABINIT、QE 等），我们可以做出一些更有力的陈述。理解 PW DFT 码的一个重要思想是哈密顿量永远不会存储为大矩阵。相反，哈密顿算子的作用被计算并用于通常是“内部”迭代对角化器（共轭梯度、戴维森等）。这些对角化器是正式的$O(n_e MV)$， 在哪里$MV$是计算哈密顿量的成本，但考虑到它们在更大的自洽算法中的作用，它们往往执行得更快。

计算哈密顿量的过程分为几个步骤：

• 真实空间中的局部电位需要 FFT，$O(n_v \ln n_v)$
• 投影可以发生在实空间或 g 空间中，$O(n_a n_p)$或者$O(n_a n_p n_v)$， 分别
• 非局部势是对角线或块对角线，$O(n_a n_p)$或者$O(n_a n_p^2)$， 分别

所有这些都必须每个电子发生一次（实际上是波函数），所以添加一个因子$n_e$对他们所有人。

通过某种方式（例如，Gram-Schmidt），波函数（哈密顿量的特征函数）必须保持相互正交，$O(n_e^2 n_v)$

最后，波函数需要组合成一个电子密度。在 PW 码中，这是通过每个波函数（和一个总和）的最后一个 FFT 来完成的，$O(n_e n_v \ln n_v)$.

请注意，我已经放入了一些不同的$n$的：$n_v$与体积有关（实际上，它是基础尺寸），$n_p$是每个原子的投影仪数量，$n_a$是原子数，并且$n_e$电子数。正式地$n_v$,$n_a$， 和$n_e$都是线性相关的（$n_p$是一个小整数），但您可以想象用固定数量的电子增加体积（在板/线几何形状中添加真空）或增加具有固定数量的原子和电子的投影仪的数量（使用更准确的赝势）。

问题通常是 FFT 限制的，在这种情况下，它们是有效的$O(n^2 \ln n)$，这在文献中是一个比较常见的答案，如果在技术上不正确的话。