问题标签 [asymptotic-complexity]

我认为复杂度将是 O(logn)。
也就是作为内循环的产物，外循环——永远不会执行超过100次，所以可以省略。

我不确定的是 while 子句，是否应该将其合并到 Big-O 复杂性中？对于非常大的i值，它可能会产生影响，或者算术运算，无论规模多大，都算作基本运算并且可以省略？

I have a question and I tried to think over it again and again... but got nothing so posting the question here. Maybe I could get some view-point of others, to try and make it work...

The question is: we are given a SORTED array, which consists of a collection of values occurring an EVEN number of times, except one, which occurs ODD number of times. We need to find the solution in log n time.

It is easy to find the solution in O(n) time, but it looks pretty tricky to perform in log n time.

有人可以帮助我使用 Big O(1) 但不是 Ω(1) 的函数吗？反之亦然？一些解释会很有帮助。

我对编程相当陌生，最近被介绍到渐近复杂性的主题。我很好奇的是，考虑到元素的数量和对它们进行排序所花费的时间，如何计算排序方法的渐近复杂度。

这是我的意思的一个例子。

• 'sortArray' 对具有 400 个元素的排序数组进行排序的时间：4
• 'sortArray' 对具有 800 个元素的排序数组进行排序的时间：8
• 'sortArray' 对具有 1600 个元素的排序数组进行排序的时间：16

• 'sortArray' 对具有 3200 个元素的排序数组进行排序的时间：26

• 'sortArray' 对具有 400 个元素的随机数组进行排序的时间：255

• 'sortArray' 对具有 800 个元素的随机数组进行排序的时间：958
• 'sortArray' 对具有 1600 个元素的随机数组进行排序的时间：4059
• 'sortArray' 对具有 3200 个元素的随机数组进行排序的时间：16585

有关如何计算此类事物的 Big O 表示法的任何帮助？谢谢！

我将证明以下示例：

值得注意的是，多项式函数比指数函数增长得更快。我们试图找到满足条件的 k0 > 0

比

所以，k0 > 0，正且足够小，而c的值无关紧要……可以吗？

我从事 RTOS 和 Linux 驱动程序开发已经有一段时间了。现在我正在半导体公司面试，但未能回答有关字符串算法以及时间和空间复杂性的问题。因为我有电子背景，所以我没有学习离散数学和算法。

我怎样才能克服这个差距？

想象一下，你和一只猫在一座高楼里。猫可以从低层窗户掉下来幸存下来，但如果从高地板上摔下来就会死。你怎么能用最少的尝试次数计算出猫可以存活的最长跌落？

显然，如果你只有一只猫，那么你只能线性搜索。先把猫从一楼扔出去。如果它幸存下来，从第二个扔掉它。最终，从 f 楼被扔下后，猫会死去。然后您就知道 f-1 层是最大安全层。

但是如果你有不止一只猫怎么办？您现在可以尝试某种对数搜索。假设该建筑有 100 层，而您有两只相同的猫。如果你把第一只猫扔出 50 层而它死了，那么你只需要线性搜索 50 层。如果您第一次尝试选择较低的楼层，您可以做得更好。假设您选择一次解决 20 个楼层的问题，而第一个致命楼层是 #50。在这种情况下，您的第一只猫将在 20 层和 40 层的飞行中幸存下来，然后从 60 层死亡。您只需分别检查 41 到 49 层。总共尝试了 12 次，这比尝试使用二元消除时需要的 50 次要好得多。

一般来说，对于有 2 只猫的 n 层建筑，最好的策略和最坏情况的复杂性是什么？n 层楼和 m 只猫呢？

假设所有的猫都是等价的：它们都会因从给定的窗户掉下来而存活或死亡。此外，每一次尝试都是独立的：如果一只猫从跌倒中幸存下来，它就完全没有受伤。

这不是家庭作业，尽管我可能曾经为学校作业解决过它。这只是今天突然出现在我脑海中的一个异想天开的问题，我不记得解决方案了。如果有人知道这个问题的名称或解决方案算法的名称，则可以加分。

语句“算法 A 的最坏情况运行时间”和“算法 A 的运行时间为 O(n)”之间有区别吗？

我认为“没有区别”，因为最坏的情况是函数可以占用的峰值运行时间，O(n) 表示该函数是“有界的”。两者给出相同的含义。

希望我的逻辑是正确的。

O 代表大 O。

O(g) : { f| f 是非负函数
             ，存在 c,m，其中 c 和 m 是任何常数
             ，使得 f(n) <= cg(n) for all n >= m } 证明

           ：- O( f(n) + g(n ) ) = O( 最大{ f(n) , g(n) } ) 。

我花了很多时间在这里和 math.stackexchange 上阅读有关 Big-Oh 的问题和答案，似乎这是最好的地方，因为 math.stackexchange 似乎不喜欢这类问题。所以我在大学的CS课程上得到了一些课程作业，我并不完全理解它，希望你们能提供帮助。我知道“家庭作业”问题在这里有点不受欢迎，所以我选择了另一个不属于我的课程但风格相似的例子。

所以这是我在笔记中给出的定义：

我得到的问题是：

使用定义 2.5 表明如果 f(n) 为 O(g(n))，则 k + f(n) 也是 O(g(n))。

我花了 3 天时间在网上搜索此类问题的任何答案。查看定义 2.5，它说 f(n) 是 O(g(n))，k + f(n) 是 O(g(n))。这对我来说已经足够了，但似乎我必须证明它是如何得出的。起初我认为它应该以某种方式通过归纳来完成，但后来决定反对，必须有一种更简单的方法。

任何帮助，将不胜感激。我不指望有人会直截了当地给我答案。我更喜欢方法论或参考，以了解我可以在哪里学习这样做的技术。我能否再次提醒您，这不是我的实际课程作业，而是类似风格的问题。

提前致谢。