用 n 个动作强制执行 O(n^2) 次操作（重新分配）
Forcing O(n^2) operations with n actions (Reallocation)
我必须安置未知数量的人（此处无关紧要）。
我有无数个房间，每个房间可以容纳两个人（2、4、8、...）。而且，我一次只能买一间房。
每次房间都变得太小 房间 A 中的每个人都必须移动到更大的 房间 B。当房间只有一半时会发生相同的过程。在这种情况下，每个人都必须从 房间 B 回到 房间 A。
现在有一个人破解了我的策略并输入了错误的 "enter-/leave-" 操作，以至于实际容纳的人数是错误的（或多或少）。
我已经证明可以用 n "enter/leave"-actions 强制 O(n^2) 人换房间（n 是进入和离开的次数 - 动作） .
这里注意，一个人换房间x次算换房间x次。
首先执行 n/2 回推操作
那么房间里有n/2个人
然后n/4（pushBack + popBack）
对于每个 pushBack，分配一个大小为 n 的房间，n/2 人是 "copied"
对于 popBack，分配了一个较小的房间，大小为 n/2，剩下的每个 n/2 人都被复制到里面。
对于一个 (pushBock + popBock)-operation 有 n 个操作完成 (coping)
所有操作（移动除外）的总工作量为 O(n)
这意味着对于n个操作，至少有(n/4)*n = Θ(n^2)个复制操作
我必须安置未知数量的人（此处无关紧要）。
我有无数个房间，每个房间可以容纳两个人（2、4、8、...）。而且，我一次只能买一间房。
每次房间都变得太小 房间 A 中的每个人都必须移动到更大的 房间 B。当房间只有一半时会发生相同的过程。在这种情况下，每个人都必须从 房间 B 回到 房间 A。
现在有一个人破解了我的策略并输入了错误的 "enter-/leave-" 操作，以至于实际容纳的人数是错误的（或多或少）。 我已经证明可以用 n "enter/leave"-actions 强制 O(n^2) 人换房间（n 是进入和离开的次数 - 动作） .
这里注意，一个人换房间x次算换房间x次。
首先执行 n/2 回推操作
那么房间里有n/2个人
然后n/4（pushBack + popBack）
对于每个 pushBack，分配一个大小为 n 的房间，n/2 人是 "copied"
对于 popBack，分配了一个较小的房间，大小为 n/2，剩下的每个 n/2 人都被复制到里面。
对于一个 (pushBock + popBock)-operation 有 n 个操作完成 (coping)
所有操作（移动除外）的总工作量为 O(n)
这意味着对于n个操作，至少有(n/4)*n = Θ(n^2)个复制操作