algorithm - while循环时间复杂度-6ren

algorithm - while循环时间复杂度

转载作者：塔克拉玛干更新时间：2023-11-03 06:02:35

27

4

我有一个算法考试..并且在循环时间复杂度方面不太好 :s 我刚刚开始了解它的基础知识..

我有这个 while 循环

i=2
while (i<n)
{
   i=i*i
   x=x+1
}

我相信解决方案一定是这样的:
(i) 将从 2 运行到 2^k 其中 k = 2ⁱ
每次执行语句1次..

所以 1+1+1+.. ，这意味着 1*2^k

从这里我无法继续..

第二个问题伙计们..请推荐一个我可以练习更多这些的网站或某物..搜索但没有找到:s

最佳答案

只要 i 小于 n，循环就会运行。换句话说，您需要找到满足 2^{2^k} < n 的 k。 ==> k = log₂log₂n。所以循环迭代 log₂log₂n 次并且在每次迭代中它执行 2 个操作(乘法和加法)——这些操作需要 O(1) 时间。

==> 执行循环的时间等于 log₂log₂n * O(1) ==> 总复杂度为 O( loglogn).

关于algorithm - while循环时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15184862/

27

4

0

文章推荐： performance - 递归伪代码的时间复杂度

文章推荐： php - 从PHP中的经纬度获取位置

文章推荐： PHP 如果变量不为空，则在每个变量后显示逗号

文章推荐： c# - 多次比较字符串

java - 为什么使用排序(O(n log n) 复杂度)比使用 HashMap(O(n) 复杂度)更快地找到多数元素？
多数元素问题: Given an array of size n, find the majority element. The majority element is the element tha
java - LinkedHashMap 复杂度
我有一个简单的问题来找到数组 A 中的第一个唯一元素。但是，令我困扰的是使用不同方法的时间复杂度。到目前为止，我已经尝试过这两种方法。第一种方法: LinkedHashMap> map = new
c++ - valarray 复杂度
STL 中valarray::min 和valarray::max 函数的时间复杂度是多少？此外，什么是查找各种其他 STL 组件的时间/空间复杂性的良好来源？最佳答案 O(N) 这些函数不会缓存
algorithm - 复杂度 - 输入长度
我目前正在学习复杂性(或效率，不管你怎么调用它)，我在我得到的一本书中读到了它。写了一些我觉得很无意义的东西，我需要一个解释。我试过在线查找，但我没有找到他们给出的这个特定示例的答案。 For an
algorithm - 算法分析(复杂度)
如何分析算法？是什么让快速排序具有 O(n^2) 的最坏情况性能，而合并排序具有 O(n log(n)) 的最坏情况性能？最佳答案这是整个学期的主题。最终，我们讨论的是在算法完成之前必须完成的操作
SQL `LIKE` 复杂度
有谁知道最流行的数据库的 SQL LIKE 运算符的复杂度是多少？最佳答案让我们分别考虑三个核心案例。此讨论是特定于 MySQL 的，但也可能适用于其他 DBMS，因为索引通常以类似的方式实现。
go - `append` 复杂度
Go 编程语言中这个循环的计算复杂度是多少？ var a []int for i := 0 ; i doublecap { newcap = cap } else {
c++ - unordered_map 复杂度
我需要创建一个查找函数，其中 (X,Y) 对对应于特定的 Z 值。对此的一个主要要求是我需要尽可能接近 O(1) 复杂度。我的计划是使用 unordered_map。我通常不使用哈希表进行查找，因为
Python 字典键。 "In"复杂度
快速提问，主要满足我对该主题的好奇心。我正在编写一些带有 SQlite 数据库后端的大型 python 程序，并且将来会处理大量记录，因此我需要尽可能优化。对于一些功能，我正在通过字典中的键进行搜
go - `append` 复杂度
Go 编程语言中这个循环的计算复杂度是多少？ var a []int for i := 0 ; i doublecap { newcap = cap } else {
performance - 方法的大 O 复杂度
我有这个方法: public static int what(String str, char start, char end) { int count=0; for(int i=0;
java - 嵌套循环的大 O 复杂度
for (i = 0; i i; j--) //some code that yields O(1) } 我认为上面的代码会产生 n*log(n) 但我看到另一个消息来源说它真的是 n^2
mysql - OFFSET 复杂度 InnoDB
我对 InnoDB 中 OFFSET 的复杂性有疑问。我知道这主要适用于线性复杂性，但如果我在字段上有索引？! 示例: CREATE TABLE `person_rand` ( `p_id` int
javascript - 如何降低 if/else 复杂度？
我嵌套了一些 if/else 语句，但我想减少它们的开销。在示例中，我正在评估从哪个下拉列表中单击了 li 项目，以及该 li 项目是否是第一个 (currentIndex === 0)。代码:
java - 基数排序(java实现)复杂度
这是我的第一个问题，所以我希望我没有违反任何规则。我终于设法为基数排序算法编写代码，但我想知道我是否做错了。让我觉得我的算法看起来复杂度为 O(n^3)，但众所周知，基数排序是一个 O(k.n) 算法
algorithm - 降低排序算法中的大 O 复杂度
几周前我认识了 big-O 并试图掌握它，但是尽管有很多关于计算时间复杂度的 Material ，但我似乎无法找到如何使算法更高效。我一直在练习 Codility 中的演示挑战: Write a f
algorithm - 计算大 O 复杂度
在最近的一次考试中，我们得到了一个函数来计算在未排序的 ArrayList 中出现了多少个 double (不是原始 double，而是一个项目出现两次的次数)。我正确地确定了 Big O 复杂度为
algorithm - 此循环的大 O 复杂度
以下循环的大 O 复杂度是多少: for each vertex u ∈ C do for each vertex v ∈ C and v > u do 我在这里做的是想象以下集合 {
algorithm - 算法中的大 O 复杂度
我想对条款进行排序，使每个条款都是下一个条款的大 O √n√logn √n log⁡( n^30) n/〖(logn)〗^2 〖16〗^(log√n) 谁能帮忙找到顺序？最佳答案 claim :16
algorithm - 计算这个选择排序实现的大 O 复杂度？
我正在尝试计算此选择排序实现的大 O 时间复杂度: void selectionsort(int a[], int n) { int i, j, mini

首页

博学

6Ren·AI

商城

algorithm - while循环时间复杂度