排序或非整数数组的复杂性
Complexity on sorting or not an integer array
我有一个整数数组存储一些用户 ID。我基本上是想阻止用户执行两次操作，所以在他完成操作后，他的用户 ID 就会进入这个数组。
我想知道对这个数组进行排序是否是个好主意。如果已排序，则有 A={min, ..., max}。然后，如果我没记错的话，检查一个 ID 是否在数组中将花费 log2(|A|) 'steps'。另一方面，如果数组未排序，则您将需要 |A|/2（平均）步。
所以排序似乎更好地检查数组中是否存在元素（log(|A|) vs |A|），但是 'adding' 一个新值呢？计算新用户 ID 的位置可以在检查的同时完成，但是你必须将所有元素从该位置移动 1 ... 或者至少我会这样做在 C 上，事实是这将是 MongoDB 文档中的一个数组，所以也许这是以其他一些最有效的方式处理的。
当然，如果数组未排序，那么添加一个新值只需一步（"pushing"它到最后）。
对我来说，加法操作（经过之前的检查）需要：
- 如果排序：
log2(|A|) + |A|/2。 log2 部分用于检查和查找位置，|A|/2 作为所需位移的平均值。
- 如果未排序：
|A|/2 + 1。 |A|/2 检查，+1 推送新元素。
鉴于添加总是先检查，然后未排序的版本似乎步骤较少，但事实是我对排序版本的 +|A|/2 不是很有信心。这就是我在 C 中的做法，但也许它可以用另一种方式工作...
O(Log(A)) 肯定比O(A) 好，但这可以在O(1) 中完成。如果您要在 C 中执行此操作，您正在寻找的数据结构是 HashMap。我已经很长时间没有在 C 中工作了，所以我不知道它现在是否是本地可用的。它肯定在 C++ 中可用。还有一些库可以在最坏的情况下使用。
对于 MongoDB，我的解决方案可能不是最好的，但我认为您可以创建另一个仅包含 userID 的集合并索引以 userID 为键的集合。这样当有人试图执行该操作时，您可以最快地查询用户状态。
同样在 MongoDB 中，您可以尝试将另一个名为 UserDidTheAction 的 key 添加到您的用户集合中。此键的值可能为 true 或 false。根据 userID 索引集合，您可能会获得与其他解决方案相似的性能，但代价是修改原始集合的设计（尽管不需要在 MongoDB 中修复）。
我有一个整数数组存储一些用户 ID。我基本上是想阻止用户执行两次操作，所以在他完成操作后，他的用户 ID 就会进入这个数组。
我想知道对这个数组进行排序是否是个好主意。如果已排序，则有 A={min, ..., max}。然后，如果我没记错的话，检查一个 ID 是否在数组中将花费 log2(|A|) 'steps'。另一方面，如果数组未排序，则您将需要 |A|/2（平均）步。
所以排序似乎更好地检查数组中是否存在元素（log(|A|) vs |A|），但是 'adding' 一个新值呢？计算新用户 ID 的位置可以在检查的同时完成，但是你必须将所有元素从该位置移动 1 ... 或者至少我会这样做在 C 上，事实是这将是 MongoDB 文档中的一个数组，所以也许这是以其他一些最有效的方式处理的。
当然，如果数组未排序，那么添加一个新值只需一步（"pushing"它到最后）。
对我来说，加法操作（经过之前的检查）需要：
- 如果排序：
log2(|A|) + |A|/2。log2部分用于检查和查找位置，|A|/2作为所需位移的平均值。 - 如果未排序：
|A|/2 + 1。|A|/2检查，+1推送新元素。
鉴于添加总是先检查，然后未排序的版本似乎步骤较少，但事实是我对排序版本的 +|A|/2 不是很有信心。这就是我在 C 中的做法，但也许它可以用另一种方式工作...
O(Log(A)) 肯定比O(A) 好，但这可以在O(1) 中完成。如果您要在 C 中执行此操作，您正在寻找的数据结构是 HashMap。我已经很长时间没有在 C 中工作了，所以我不知道它现在是否是本地可用的。它肯定在 C++ 中可用。还有一些库可以在最坏的情况下使用。
对于 MongoDB，我的解决方案可能不是最好的，但我认为您可以创建另一个仅包含 userID 的集合并索引以 userID 为键的集合。这样当有人试图执行该操作时，您可以最快地查询用户状态。
同样在 MongoDB 中，您可以尝试将另一个名为 UserDidTheAction 的 key 添加到您的用户集合中。此键的值可能为 true 或 false。根据 userID 索引集合，您可能会获得与其他解决方案相似的性能，但代价是修改原始集合的设计（尽管不需要在 MongoDB 中修复）。