Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
質問があります:
オブジェクトを含む配列"S"がありnます。また、各オブジェクトにはmフィールドがあります。のような別の配列にそれらのいくつかを保存したい"Q"。この簡単な方法のスペースの複雑さはO(|Q|)?
"S"
n
m
"Q"
O(|Q|)
sスペースの複雑さは、 Qを格納するために必要なスペースの量ですs = size of all m fields。スペースの複雑さはO(n*s)です。すべてのフィールドが同じ一定サイズの場合は、O(n*m).
s
s = size of all m fields
O(n*s)
O(n*m)
Sサイズですn*sum(sizeofeach(m of n))
n*sum(sizeofeach(m of n))
次に、r オブジェクトをどこに保存するとします。r<n
r<n
qの大きさはr*(sum(sizeofeach(m of r))
r*(sum(sizeofeach(m of r))