复杂度O（log（n））是否等于O（sqrt（n））？
我的教授刚刚告诉我们，任何将输入长度减半的运算都具有O（log（n））复杂度，这是经验法则。为什么不是O（sqrt（n）），两个都不相等？
问题答案：
它们不是等效的： sqrt（N）的 增长将比 log 2（N）_大得多。没有常数 _C， 因此对于所有大于某个最小值的 N 值，您都将拥有
sqrt（N） <C.log（N）。 __
一个简单的方法来抓住这个，是 日志 2（N）_将是一个值接近的（二进制）位的数目 _Ñ ，而 SQRT（N）
将是一个数，其具有自身的位数的一半数量的 Ñ 具有。或者，用等式声明：
log 2（N）= 2log 2（sqrt（N））
因此，您需要使用 sqrt（N） 的对数（！）使其复杂度降低到与 _log 2（N）_相同的顺序。
例如，对于11位二进制数字0b10000000000（= 2 10），平方根为0b100000，但对数仅为10。
-
查找p的伪码算法为： 假设我有一个int值的数组H[1到m]，其中“p”是峰值元素，如果： 基本上，如果H【p】大于或等于其相邻元素，则H【p】为峰值。 假设数组H在开始和结束时都大于1个元素，数组为H[0到m 1]，其中H[0]=H[m 1]=无穷大。因此，H[0]和H[m 1]是哨兵。然后是元素p，其中1≤ p≤ n、 是一个峰值，如果H【p-1】≤ H【p】≥ H【p 1】。 我认为渐近时间
-
Redis zrank。 返回存储在key处的排序集中成员的排名，分数从低到高排序。排名（或指数）是基于0的，这意味着得分最低的成员排名为0。 为什么复杂度是O（log（N））？成员按分数排序，但zank按成员查询。 我找到了一些可能是答案的东西。 A.zset由ziplist实现时 大小小于128 每个成员的大小小于64字节 所以，ziplist的大小很小，所以这不是我讨论的问题。 B.当zse
-
问题内容： 我刚刚开始学习数据结构，并且在进行数组插入时想知道为什么数组插入的时间复杂度为O（n）而不是O（n + 1）？ 在最佳情况下，当插入在最后时，时间复杂度为O（1）。我想我们正在考虑1插入元素，因为这里没有元素被移动。在最坏的情况下，假设我们必须移动n个元素然后插入新元素，那么时间时间复杂度是否应该为O（n + 1）？n用于移动元素，1用于插入。 非常感谢您的帮助。 问题答案： O（n）
-
就像谷歌地图一样，给定一百万个经纬度坐标列表，你将如何打印距离给定位置最近的k个城市？ 我在一次面试中问了这个问题。面试官说这可以在O（n）中通过使用插入排序到k来完成，而不是对整个列表进行排序，即NlogN。我在网上找到了其他答案，大多数人都说NLogN...他[面试官]正确吗？
-
我试图为这段代码找出一个大O的紧密界限： 如果我们从内最循环开始，它将在最坏的情况下运行k=n^2次，占O（N^2）。如果语句每次j=m*i时都为真，其中m是一个任意常数。由于j从1运行到i^2，这将在m={1,2，...，i}时发生，这意味着它将在i次时为真，i最多可以是n，所以最坏的情况将是m={1,2，...，n}=n次。如果i=n，第二个循环应该有O（N^2）的最坏情况。外环具有O（N）的
-
描述一个O（n logn）-时间算法，给定一组由n个整数和另一个整数x组成的S，该算法确定S中是否存在两个元素，其和正好是x。 我计划用二进制搜索来搜索这个。 我如何找到这个算法的时间复杂度？如果T（n）不是（n log n），正确的算法是什么？
-
我在GeekforGeekshttps://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/中检查“到达终点的最小跳跃次数”问题。我对这里提到的时间复杂度感到困惑，它是O（n^n）。 如果我看到上面的代码块，minJumps（arr，I，h）递归调用是从I=l1调用的。所以在每个递归步骤中，l（
-
即使在最坏的情况下，是否有任何数据结构可以提供O（1）——即常数——插入复杂性和O（log（n））搜索复杂性？ 排序后的向量可以进行O（log（n））搜索，但插入需要O（n）（考虑到我并不总是在前面或后面插入元素这一事实）。而列表可以进行O（1）插入，但不能提供O（log（n））查找。 我想知道这样的数据结构是否可以实现。