如果你有一个固定大小的数组，你需要遍历它 !n 次，使用二分查找如何改变时间复杂度？
If you have an array of fixed size, and you need to go through it !n number of times, how does using binary search change the time complexity?
我们想要找到长度为 n 的字符串的所有排列。然后，您要搜索一个固定常量大小的数组，比如 3000 并检查该字符串是否在数组中。
String arr[3000];
因为我们将有 !n 个排列，所以我们需要进行 !n 次搜索。
此外，当您根据数组中的元素检查 2 个不同的字符串与仅检查 1 个字符串时有什么区别？
时间复杂度是多少？
我的想法是，最坏的情况是 log2(3000) 遍历数组一次。其时间复杂度为 O(log2(3000))，即 O(1)。
现在，您需要遍历此数组 !n 次，因此时间复杂度为 O(!n)。
因此，在分析该算法的时间复杂度时，减少所需搜索次数的二分查找不应成为重点。
我的问题是，二分搜索确实减少了搜索次数，如果您要进行 n! 次，这应该不会有显着差异吗？
感谢任何有助于我理解的见解。
Big O 复杂性分析仅处理可能发生变化的数量，根据定义。当您的所有数量都恒定时，您会得到空洞的答案。
当比较两个相等的 Big-O 算法时，常数因子 是相关的，所以你从 3000 -> log2(3000) 的变化是一个大约 200 的因子。
因此，您使用二分查找是因为您所做的不仅仅是 Big-O 分析。您还估算了常数因子，并看到了轻松的 200 倍加速
但同样，您的复杂性可以有多个术语。你可能会说：
- 设
n为输入字符串长度
- 设
m 为 arr 的大小
- 我们的算法是
O( n * n! * log(m) )（n 用于字符串相等，n! 用于排列，log(m) 用于二进制搜索）
它还相当依赖于成本的模型。通常这会映射回一些抽象机器，例如我们假设操作有一定的成本。例如。您可以通过 just 比较计数，或 just 交换计数，或 计数来比较排序算法比较和交换.
我们想要找到长度为 n 的字符串的所有排列。然后，您要搜索一个固定常量大小的数组，比如 3000 并检查该字符串是否在数组中。
String arr[3000];
因为我们将有 !n 个排列，所以我们需要进行 !n 次搜索。
此外，当您根据数组中的元素检查 2 个不同的字符串与仅检查 1 个字符串时有什么区别？
时间复杂度是多少？
我的想法是，最坏的情况是 log2(3000) 遍历数组一次。其时间复杂度为 O(log2(3000))，即 O(1)。
现在，您需要遍历此数组 !n 次，因此时间复杂度为 O(!n)。
因此，在分析该算法的时间复杂度时，减少所需搜索次数的二分查找不应成为重点。
我的问题是，二分搜索确实减少了搜索次数，如果您要进行 n! 次，这应该不会有显着差异吗？
感谢任何有助于我理解的见解。
Big O 复杂性分析仅处理可能发生变化的数量，根据定义。当您的所有数量都恒定时，您会得到空洞的答案。
当比较两个相等的 Big-O 算法时，常数因子 是相关的，所以你从 3000 -> log2(3000) 的变化是一个大约 200 的因子。
因此，您使用二分查找是因为您所做的不仅仅是 Big-O 分析。您还估算了常数因子，并看到了轻松的 200 倍加速
但同样，您的复杂性可以有多个术语。你可能会说：
- 设
n为输入字符串长度 - 设
m为arr 的大小
- 我们的算法是
O( n * n! * log(m) )（n用于字符串相等，n!用于排列，log(m)用于二进制搜索）
它还相当依赖于成本的模型。通常这会映射回一些抽象机器，例如我们假设操作有一定的成本。例如。您可以通过 just 比较计数，或 just 交换计数，或 计数来比较排序算法比较和交换.