array.contains 数组类型大小的运行时间
array.contains runtime in terms of size of array type
假设我有两个等长的数组，一个是 x 类型，另一个是 y 类型，x 是 y 内存中大小的一半。如果我生成了 2 个对象，一个是 x 类型，另一个是 y 类型，并检查它们各自的数组是否包含它们，平均而言，这两个操作会花费相同的时间吗？
这个时间可以通过使用另一个（有序的）数据结构来改善吗？
在无序数组中搜索给定元素具有 O(n) 复杂性，这意味着它与元素数量呈线性相关。 它不依赖于元素的大小，因为数组具有恒定的随机访问时间（数组中第 n 个元素的地址可以使用简单的指针算法计算）。
所以是的，搜索这 2 个对象平均需要花费相同的时间。或者更准确地说 - 具有相同的复杂性（线性）。
通过有序数据结构（例如排序列表或二叉树）进行搜索允许使用 O(log (n)) 算法（二分搜索），平均而言，这种算法要快得多。
参考this cheatsheet了解一些常见的数据结构和对它们执行操作的复杂性。
使用hash-table/hash-set。预期或估计的查找是 O(1) 假设比较两个对象是 O(1).
但一般来说，大 2 倍的对象可能需要多 2 倍的时间进行比较。但是它不会影响数组查找时间，因为在该操作期间您使用的是索引，而不是对象本身
我的系统教授回答了这个问题：
If the work time is bounded on the number of instructions, then the exhaustive searches on the two arrays yield equal time.
If the work time is bounded on the memory access speed, then search on the larger array (here "larger" means more bytes) takes more time.
Whether the work time is instruction-bound or memory access-bound may depend on the compiler. A poor compiler may produce many instructions such that the time is instruction-bound.
假设我有两个等长的数组，一个是 x 类型，另一个是 y 类型，x 是 y 内存中大小的一半。如果我生成了 2 个对象，一个是 x 类型，另一个是 y 类型，并检查它们各自的数组是否包含它们，平均而言，这两个操作会花费相同的时间吗？
这个时间可以通过使用另一个（有序的）数据结构来改善吗？
在无序数组中搜索给定元素具有 O(n) 复杂性，这意味着它与元素数量呈线性相关。 它不依赖于元素的大小，因为数组具有恒定的随机访问时间（数组中第 n 个元素的地址可以使用简单的指针算法计算）。
所以是的，搜索这 2 个对象平均需要花费相同的时间。或者更准确地说 - 具有相同的复杂性（线性）。
通过有序数据结构（例如排序列表或二叉树）进行搜索允许使用 O(log (n)) 算法（二分搜索），平均而言，这种算法要快得多。
参考this cheatsheet了解一些常见的数据结构和对它们执行操作的复杂性。
使用hash-table/hash-set。预期或估计的查找是 O(1) 假设比较两个对象是 O(1).
但一般来说，大 2 倍的对象可能需要多 2 倍的时间进行比较。但是它不会影响数组查找时间，因为在该操作期间您使用的是索引，而不是对象本身
我的系统教授回答了这个问题：
If the work time is bounded on the number of instructions, then the exhaustive searches on the two arrays yield equal time.
If the work time is bounded on the memory access speed, then search on the larger array (here "larger" means more bytes) takes more time.
Whether the work time is instruction-bound or memory access-bound may depend on the compiler. A poor compiler may produce many instructions such that the time is instruction-bound.