-
1 votesanswersviews
Ids算法的空间复杂度
您好我尝试计算IDS(迭代深化深度优先搜索)算法的空间复杂度,但我无法弄清楚如何做到这一点 . 我无法真正理解算法如何访问树的节点,以便我可以计算它所需的空间 . 你能帮助我吗? -
2 votesanswersviews
在二叉树上进行广度优先搜索的空间复杂度是多少?
这是我的Java解决方案,用于逐级打印二叉树,并进行广度优先搜索(它可以正常工作!!) public void printByLevel() { System.out.print("Elements By Level:"); if(overallRoot!= null) { Queue<IntTreeNode> bfs = new L... -
2 votesanswersviews
这种添加是否会保留DFS的空间和时间复杂度?
所以我为节点树实现了标准的深度优先搜索,其中每个节点封装了我正在解决的问题的状态,我还添加了下面的方法来检查我是否不会通过扩展节点来重复移动封装了我之前在某个节点中检查过的状态 . 我的问题是:这种方法是否会以某种方式改变算法的时间或空间复杂度,或者它们仍然是典型的DFS O(b ^ m)和O(bm)(这里b - 分支因子和m - 最大深度) . //additional method whi... -
0 votesanswersviews
2-3树中的最小和最大节点数
我试图找出具有n个叶子的2-3树中的最小和最大节点数 . 我试过用inf \ sup来阻止它,但是我不能再进一步说明2-3树中的节点数量大于完整AVL树中的节点数量 . 提前致谢 -
1 votesanswersviews
矩阵时间复杂度分析中最长的增长路径
我正在研究下面的算法: Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or mo... -
1 votesanswersviews
广度优先搜索的时空复杂性
我只是想检查一下我对Russell和Norvig中给出的算法和计算的理解是否正确 . 我使用传教士和食人族作为测试时间和空间复杂性的问题 . 计算深度并不是什么大不了的事 . 我总是在深度11处找到解决方案 . 我无法解决的问题是分支因素 . Russell和Norvig第82页说: “探索集合中将有O(b ^(d-1)个)节点,边界中有O(b ^ d)个节点......” 我的程序在探索的集... -
5 votesanswersviews
为什么这个算法的空间复杂度是O(1)
大家好:我阅读下面的算法,找到二叉搜索树中两个节点的最低共同祖先 . /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; ... -
-2 votesanswersviews
计算函数的空间复杂度和时间复杂度
作为课程作业的一部分,我需要计算程序的复杂性 . 我想计算下面程序的空间复杂度和时间复杂度 . 我如何计算它?如果有人可以详细解释它,对我来说真的很有帮助 . sub find_multi_string { my ($file, @strings) = @_; my $fh; open ($fh, "<$file"); #store th... -
4 votesanswersviews
如何计算空间复杂度来打印二叉树中给定值求和的所有路径
这个问题来自Cracking the Coding Interview,我无法理解为其解决方案指定的空间复杂性 . Problem: 您将获得一个二叉树,其中每个节点都包含一个值 . 设计一种算法来打印总和为给定值的所有路径 . 请注意,路径可以在树中的任何位置开始或结束 . Solution (in Java): public static void findSum(TreeNode node,... -
3 votesanswersviews
空间复杂性示例
所以我想知道在for循环中何时创建对象(或基元),这对空间复杂性有何影响? 例如,下面是一个代码示例: public boolean checkUnique(String p){ int term = -1; int len = p.length(); for (int i =0; i<len; i++) { char c = p.charAt(i);... -
0 votesanswersviews
时间复杂度与空间复杂性
我试图从短算法中理解时间和空间复杂性之间的差异 . 此代码采用列表/数组并返回发生奇数次的单个数字 . 在Python中: def foo(array_of_ints): hash_table = dict() for i in array_of_ints: hash_table[i] = hash_table.setdefault(i, 0) + 1 fo... -
0 votesanswersviews
TextRank算法空间和时间复杂度
我试图确定TextRank的空间和时间复杂度本文中列出的算法:https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf 由于它使用的PageRank的复杂度为:O(nm)(n - 节点数,m - 弧/边数),我们在迭代中运行它/直到收敛关键字提取的复杂性我认为它将是:O (i *(nm))并且使用邻接矩阵将空间复杂度设为O... -
9 votesanswersviews
深度优先搜索的时间/空间复杂性
我查看了其他各种StackOverflow答案,它们都与我的讲师在幻灯片中写的不同 . 深度优先搜索的时间复杂度为O(b ^ m),其中b是搜索树的最大分支因子,m是状态空间的最大深度 . 如果m比d大得多,但是如果搜索树是“浓密的”,则可能比广度优先搜索快得多 . 他继续说.. 空间复杂度为O(bm),即动作序列长度的空间线性!只需存储从根节点到叶节点的单个路径,以及路径上每个节点的剩余未... -
1 votesanswersviews
具有与质数数量成比例的数据的主筛的空间复杂性是多少?
我正在练习编写针对空间或时间复杂度优化的算法 . 使用优质筛,至少您必须存储所有找到的素数列表 . 似乎与发现的素数成比例的数据是这种算法可能使用的最小空间量 . 这个理由有效吗? 如何评估此算法的空间复杂度? From Wikipedia about the sieve of Atkin - 我不确定的是,当素数超过此值时,筛子如何使用O(n ^ 1/2)空间 . 这就是为什么它似...