数学中一个空间不是稠密就是稀疏对不对

Question

如题所述

Answer 1

郭敦顒回答：
百度文库——
空间稠密性与稀疏性的概念
集图。(P441－442)
《数据结构与算法――面向对象的C++设计模式》 电子工业出版社 [美]Bruno R.Preiss著 胡广斌 王崧 惠民等译
注：（P26）定义3.1（大O表示法）
设对一切n>=0的整数有一个非负函数f(n)，如果存在一个整数n0和一个正常数c，且对任意的n>=n0有f(n)<=cg(n),那么就说“f(n)是g(n)的大O表示”，记为f(n)=O(g(n)).如f(n)=8*n+128,存在c=1,n0=16,对于任意的n>=n0 ,f(n)<=cn*n,故f(n)=O(n*n). (P34)定义3.3(Ω表示法)
设对一切n>=0的整数有一个非负函数f(n)，如果存在一个整数n0和一个正常数c，且对任意的n>=n0有f(n)>=cg(n),那么就说“f(n)是g(n)的Ω表示”，记为f(n)=Ω(g(n)).如f(n)=5n*n-64n+256,存在c=1,n0=0,对一切n>=n0,f(n)>=cn*n. (P37)定义3.4（
Θ表示法）
设对一切n>=0的整数有一个非负函数f(n)，当且仅当f(n)既是O(g(n))又是Ω(g(n))时，才说“f(n)是g(n)的
Θ表示”，记为f(n)= Θ(g(n)).
例如f(n)=3n*n+4n+3 为O(n*n),也为Ω(n*n),所以f(n)=
Θ(n*n).

我的理解：从上面的几种说法可以看出，稀疏图和稠密图均是对顶点n比较大时才有的称呼，对n很小就无所谓“稀疏”或“稠密”。因此对顶点很少的图（如n=2）讨论稀疏与稠密是没有任何意义的 。