循环遍历ArrayList并将值放入HashMap的时间复杂度与仅搜索ArrayList的时间复杂度相比
循环遍历ArrayList并将值放入HashMap的时间复杂度为O(n)，其中n是ArrayList的大小。这是因为需要遍历整个ArrayList，并将每个元素放入HashMap中，这个过程需要线性时间。
与之相比，仅搜索ArrayList的时间复杂度为O(n)，其中n是ArrayList的大小。这是因为需要遍历整个ArrayList来搜索目标值，如果目标值在ArrayList中，则需要遍历整个ArrayList才能确定。
总结起来，循环遍历ArrayList并将值放入HashMap的时间复杂度与仅搜索ArrayList的时间复杂度相同，都是O(n)。
相关·内容
1回答
分析这个简单算法的正确方法
java、algorithm、big-o
给定一些字符串，ab，abc，ad，ace，ad.从文件中找出字符串S是否在字符串中。如果我想使用散列来检查S的存在。
算法分析:由于每个put操作都需要O(1) *K时间，其中K是字符串的长度，映射的建立需要O(n * K)时间，其中n是字符串的数目。查找需要恒定的时间，所以整个时间是O(n*k)。这个想法对吗？虽然我们经常说哈希表允许常量时间查找，但它通常忽略构建哈希所花费的时间。在回答这样的问题时，我应该说时间复杂度是O(n*k)，还是仅仅是O(n)？非常感谢。刚开始学习算法分析。
String line = null;
BufferedReader br = new Buffered
浏览 3提问于2014-01-27得票数 1
回答已采纳
1回答
使用两个hashmap会产生O(n平方)的算法吗？
java、algorithm、hashmap、big-o、space-complexity
我正在尝试计算出下面算法的大O时间和空间复杂度。 我认为时间复杂度是O(n)，其中n是较大的HashMap的大小。我的理解是，这3个循环使它成为O(3n)，但然后你删除常量得到O(n)。对于put和get操作，HashMaps(至少在Java语言中)是O(1)。 我认为空间复杂度是O(n)，其中n是HashMap的大小。 但这是我的问题所在。有2个HashMaps。那么，这会使空间复杂度n x n=n平方吗？ 或者是O(2n)，它变成了O(n)？ HashMap<String,Integer> magazineWordOccurrences = new HashMap<St
浏览 24提问于2019-05-21得票数 2
4回答
对数组和大O表示法求和
algorithm、sum、big-o
如何找到计算数组中求和值的算法？
是这样的吗？
Algorithm Array Sum
Input: nonnegative integer N, and array A[1],A[2],...,A[N]
Output: sum of the N integers in array A
Algorith Body:
j:=1
sum:=0
while j<N
sum := sum + a[J]
j:=j+1
end while
end Algorithm Array Sum
以及如何通过使用O表示法将其与算法的运行时间相关联
这是过去一年的考试，我需要复习一下
浏览 3提问于2009-05-24得票数 5
回答已采纳
2回答
这个算法有多复杂？
algorithm、time-complexity
我真的很难理解大学的算法复杂性分析。我的教授给了我们一些简单的代码来计算它的复杂性，这是其中之一： double minValue(double* pd, int& p, int N)
{
double minV = pd[0];
for (int i=1; i < N; i++)
if (minV > pd[i]) {
minV = pd[i];
p = i;
}
return minV;
} 有人能告诉我这有多复杂吗？我猜是O(N²)
浏览 28提问于2020-12-16得票数 0
回答已采纳
2回答
如何计算以下代码片段的复杂性？
java、algorithm
我是一个具有大O符号和算法复杂性的初学者。我正在尝试计算下面两个java方法的复杂性，这两个方法都做同样的事情。然而，其中一个会稍微快一点。
ArrayList<Person> filter1(Person x, ArrayList<Person> people){
ArrayList<Person> friends = new ArrayList<Person();
for (Person y: people) friends.add(y);
for (Person y: people) if (!x.knows(y)) friends.
浏览 2提问于2015-03-18得票数 2
1回答
理解Leetcode 1366的时间/空间复杂性
python、algorithm、sorting、data-structures、time-complexity
我已经解决了问题，但在适当的时间/空间复杂度方面遇到了一些困难。我看过“解决方案”选项卡，但答案各不相同，我不确定是否买了其中的一些。这是我的代码和通用算法-
class Solution:
def rankTeams(self, votes: List[str]) -> str:
rankings = {}
team_count = len(votes[0])
for vote in votes:
for position, team in enumerate(vote):
浏览 10提问于2022-11-05得票数 -1
回答已采纳
4回答
HashMap.containsValue()在java中的时间复杂度是多少？
java、performance、optimization、hashmap
我被要求在O(n)时间复杂度上解决一个问题：
“给定一个数字列表和数字x。查找列表中是否有任何2个数字之和为x?”
这是我的解决方案：
public class SumMatchResult {
public static void main(String[] args){
int[] numberList = {6,1,8,7,4,6};
int requiredSum = 8;
boolean isSumPresent = checkSumPresentHash(numberList,requiredSum);
if(isSumPresent) {
浏览 0提问于2013-05-26得票数 28
回答已采纳
3回答
降低这两种方法的时间复杂度？
java、algorithm
/*
* Returns true if this and other are rankings of the same
* set of strings; otherwise, returns false. Throws a
* NullPointerException if other is null. Must run in O(n)
* time, where n is the number of elements in this (or other).
*/
public boolean sameNames(Ranking other)
{
ArrayList<
浏览 2提问于2014-02-24得票数 0
4回答
迭代数组列表的时间复杂度
java、arrays、algorithm、arraylist、data-structures
我有一个数组列表，我可以遍历它。在每次迭代中，我调用get()来获取一个元素，如果该元素通过了某个条件，就会使用add()将其添加到新的数组列表中
List<Item> items = new ArrayList<Item>();
List<Item> lessItems = new ArrayList<Item>();
for(int index = 0; index < items.size(); index++){
Item toCheck = items.get(i);
if(toCheck meets some c
浏览 1提问于2016-09-17得票数 7
1回答
以下递归代码的复杂性
algorithm、recursion、time-complexity、binary-tree
试图找出为什么这段代码的复杂性是O(n)：
int sum(Node node) {
if (node == null) {
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
节点是：
class Node {
int value;
Node left;
Node right;
}
这是来自CCI的书。它不应该是O(2^n)，因为它遍历每个节点吗？
但是这个是O(2^n)，我很清楚为什么：
int f(int n) {
if (n <= 1) {
r
浏览 3提问于2016-10-22得票数 0
回答已采纳
1回答
TreeMap集合视图迭代器时间复杂度？
java、time-complexity、treemap
HashMap的所有3种集合视图迭代器(myHashMap.entrySet().iterator().next()和myHashMap.keySet().iterator().next()和myHashMap.values().iterator().next())的时间复杂度在javadoc中都有详细说明，对于这3种迭代器(n是映射的数量，c是哈希表中桶的物理数量)，O(n+c)是很好的证明。
但是，三个TreeMap集合视图的三个迭代器又如何呢？在官方的javadoc中什么都没有说。它们的复杂性是什么？我确实看过SE8源代码，但我无法从那里判断。
浏览 2提问于2018-12-07得票数 12
2回答
实现时间复杂度O(n) -搜索预排序二叉树C++
c++、recursion、time-complexity、binary-tree
二进制搜索树LCA具有函数BinarySearchTreeLCA( strArr )，它接受存储在strArr中的字符串数组，其中包含3个元素:第一个元素是一个二进位搜索树，具有一个前置遍历数组中的所有唯一值，第二个和第三个元素将是两个不同的值，您的目标是找到这两个值中最低的公共祖先。例如:如果strArr是["10，5，1，7，40，50"，"1"，"7"]，那么这棵树如下所示：
10
/ \
5 40
/ \ \
1 7 50
对于上面的输入，您的程序应该返回
浏览 8提问于2022-03-06得票数 0
回答已采纳
1回答
嵌套固定大小的循环时间复杂度是O(n)还是O(n^2)？
nested、time-complexity、big-o
我知道如果我有一个依赖于N个元素的嵌套循环，那么它的时间复杂度将是O(N^2)。 在这种情况下，我有一个固定大小的循环，嵌套在一个N循环中，如下所示： while (i < N)
while (j < 1000){
// code //
j++;
}
i++;
} 这里的时间复杂度是多少？它不是O(N^2)，但我不知道它是O(N)还是介于两者之间的某个东西。在我看来，它不是线性的。T
浏览 14提问于2020-09-21得票数 1
2回答
这个规范的线性算法？
algorithm
这是我的问题，我有些地方要问。
给出了一个随机数列，写了一个线性时间算法，以求该列表中的第四个最小数。解释为什么您的算法是线性的。
我搜索了几乎一半的网页，我所知道的是一个线性时间算法，其时间复杂度必须是O(n)。(我可能错了)我们可以用不同的算法解决上面的问题。
对数组进行排序并选择k-1元素O(n log )
使用最小堆O(n + klog n)等.
现在的问题是，我找不到任何具有O(n)时间复杂度且满足线性的算法。解决这个问题的办法是什么？
浏览 0提问于2020-07-23得票数 1
回答已采纳
6回答
为什么链表删除和插入操作具有O(1)的复杂性？不是应该是O(n)吗？
java、data-structures、collections、linked-list、time-complexity
据说，LinkedList删除和添加操作的复杂性是O(1)的。如果是ArrayList，则是O(n)。
大小为"M“的ArrayList的计算:如果我想在N个位置删除元素，那么我可以使用索引一次直接到N个位置(我不需要遍历直到N个索引)，然后我可以删除这个元素，直到此时复杂度是O(1)，那么我将不得不移动其余的元素( can移位)，所以我的复杂度将是线性的，即O(M-N+1)。因此，删除或插入在最后将给我最好的表现(如N~ M)，删除或插入在开始将是最差的(如N~ 1)。
现在大小为"M“的LisnkedList :由于我们不能直接到达LinkedList中的N个元素，为了访问
浏览 5提问于2017-03-17得票数 23
回答已采纳
1回答
如何在O(1)平均复杂度内搜索一个数字
algorithm、analysis
我知道，如果没有关键字，我们可以在线性搜索中搜索一个数字，时间复杂度为O (n)，在最好的情况下，复杂度为O (1)。如果我想在特定的平均情况下找到一个数字，搜索算法是什么？
浏览 1提问于2018-11-05得票数 0
6回答
遍历二维数组的时间复杂度是多少？
c++、arrays、algorithm、for-loop、time-complexity
遍历(行，列)一个二维数组的时间复杂度是多少？
bool check(int array [9][9])
{
int num=0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (array [i][j] == 0) {
num++;
}
}
}
return num;
}
我认为每个for loop都会取n的平方根，因此嵌套循环完全将O(n
浏览 0提问于2015-05-07得票数 6
2回答
O(n)空间复杂度到底是什么意思，它的效率有多低？
algorithm、sorting、data-structures、time-complexity、space-complexity
我对O(n)在太空中的意义有很高的理解。这意味着，对于输入为n的算法，该算法在内存中分配的额外存储空间将与n成比例增加。
因此，如果您有一个算法，它接受一个数字n作为输入，并创建一个大小为2n的数组并将其填充为全0，时间复杂度将为O(n)，空间复杂度将为O(n)，因为您正在创建一个相对于输入大小的数组(额外的存储空间)。这种理解是正确的吗？
像快速排序这样的流行排序算法的最坏情况下的空间复杂度为O(n)，因此对于任意长的数据，O(n)空间复杂度有可能产生可怕的影响吗？
浏览 1提问于2014-12-27得票数 5
5回答
在线性时间内匹配字符串
string、algorithm、pattern-matching
给定两个字符串S和T，其中T是模式字符串。查找字符串S中是否存在作为SubString的模式字符串的任何加扰形式，如果存在，则返回起始索引。
示例：
字符串S: abcdef字符串T: efd
字符串S有"def"，这是搜索字符串T的组合："efd“。
我找到了一个运行时间为O(m*n)的解决方案。我正在研究一个线性时间解决方案，其中我使用了HashMaps (静态的，为字符串T维护的，另一个是用于检查T的当前子串的先前HashMap的动态副本)。我会从失败的下一个字符开始检查。但在最坏的情况下，它的运行时间为O(m*n)。我想得到一些让它在O(m+n)时间内工作的指针
浏览 3提问于2013-07-31得票数 2
3回答
在JRE中将ArrayList<T>转换为LinkedHashSet<T>的算法是什么？
java、algorithm、hashmap、set、linkedhashset
我希望从具有重复元素的list中获得唯一元素的list，并且应该保持列表中元素的顺序。
为了实现这一点，我可以编写如下算法：
private ArrayList<T> getUnique(ArrayList<T> list)
{
// maintain a hashmap of numbers and a uniqueList to be returned(ArrayList<T>)
// Add element in result list and the hashmap if the element isn't already p
浏览 1提问于2018-09-22得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频活动推荐
腾讯云开发者
