1.4 空间复杂度和时间复杂度

  • 「固定的空间需求」 这部分主要是指那些不依赖于程序输入、输出数量和大小的空间需求。固定空间需求包括指令存储空间(存储代码所需的存储空间),存储简单变量、固定大小的结构变量(如结构体)和常量的存储空间。

  • 「可变的空间需求」 这部分包括结构变量所需要的存储空间,这些结构变量的大小依赖于所求问题的特定实例 II,同时还包含函数递归调用时所需的额外存储空间。程序 PP 在实例 II 上所需的特定存储空间表示为 SP(I)S_P(I)

  • 「空间复杂度」 任意程序的总的空间需求 S(P)S(P) 可以表示为 S(P)=c+SP(I) S(P) = c + S_P(I) 其中,cc 是一个常数,表示固定的存储空间需求。

  • 「时间复杂度」 程序 PP 所需时间 T(P)T(P) 是其编译时间和运行(或执行)时间的总和。由于编译时间不依赖于问题实例的特征,所以编译时间类似于空间复杂度中的固定空间需求部分。真正关注的只是程序的执行时间 TPT_PTP=caADD(n)+csSUB(n)+clLDA(n)+cstSTA(n) T_P = c_aADD(n) + c_sSUB(n) + c_lLDA(n) + c_{st}STA(n) 其中,ca,cs,cl,cstc_a, c_s, c_l, c_{st} 是常数,表示执行每个操作所需的时间,而 ADD,SUB,LDA,STAADD, SUB, LDA, STA 表示执行实例特征为 nn 的程序时所需的加法、减法、读取数、存入数操作的次数。

  • 「BIG O」 f(n)=O(g(n))f(n) = O(g(n)) (读作 f(n)f(n) 大 O 于 g(n)g(n))当且仅当存在整的常数 ccn0n_0,使得对于所有的 nn,当 nn0n \geq n_0 时,有 f(n)cg(n)f(n) \leq cg(n)

  • Ω\Omega f(n)=Ω(g(n))f(n) = \Omega(g(n)) (读作 f(n)f(n) omega 于 g(n)g(n))当且仅当存在正的常数 ccn0n_0,使得对于所有的 nn,当 nn0n \geq n_0 时,有 f(n)cg(n)f(n) \geq cg(n)

  • Θ\Theta f(n)=Θ(g(n))f(n) = \Theta(g(n)) (读作 f(n)f(n) theta 于 g(n)g(n))当且仅当存在正的常数 c1,c2c_1, c_2n0n_0,使得对于所有的 nn,当 nn0n \geq n_0 时,有 c1g(n)f(n)c2g(n)c_1g(n) \leq f(n) \leq c_2g(n)

results matching ""

    No results matching ""