时间复杂度分析

计算科学 表现 复杂
2021-11-30 21:01:40

我想知道以下代码的时间复杂度

假设我有一个列表 unique_element[]

有一个数组包含元素 {4,5,2,4,7,8,1,5,9,8,1}

现在根据我的代码,我想从这个数组中找出唯一元素并将这个元素存储到 unique_element[] 列表中

for(int i=0;i<arr.length.i++){
     loop body //[This code block to find the unique element]
}

现在,在从数组中找到唯一元素并将这些元素存储到 unique_element[]list 之后,我的下一个任务是对 unique_element[] 列表进行排序。

为此,我再次创建了一个 for 循环

for(int j=0;j<unique_element[].length;j++){
 loop body to sort unique_element[]
}

现在我想计算这个程序的时间复杂度。我在 O(n^2) 和 O(n) 之间感到困惑。因为有两个循环,所以它可能是 O(n^2),但据我所知,如果有嵌套的 for 循环,那么时间复杂度将是 O(n^2)。然而,在我的程序中,two for loops它们是独立的 for 循环。因此,时间复杂度很有可能是 O(n)。

哪个是正确的 O(n^2) 或 O(n)?

先感谢您。

2个回答

这是 O(n),但这取决于您使用的排序算法。使用哈希表查找唯一元素是 O(n)。您使用一个 for 循环来计算事件,然后使用一个后续循环来提取唯一性。

排序应该卸载到库算法,因此不需要 for 循环。使用插入排序或其同类将需要 O(n^2) 时间的两个循环,但对于小型数据集,您将获得良好的性能。大多数排序算法在 O(n log n) 时间内运行,但不能使用简单的循环轻松表达。但是,因为你有整数数据,你可以使用像基数这样的社会目的排序算法,它给 O(n) 时间。

在最坏的情况下,按顺序搜索数组中的元素的时间复杂度为 O(n),因为您想象遍历整个列表以在末尾获取一个元素或找出您正在搜索的元素不存在. O(n) 是因为搜索操作随着数组大小的增长而线性增长。在最坏的情况下,对于 100 个数组元素,您需要进行 100 次操作,对于 1000000 个数组元素,您需要进行 1000000 次操作等。有几种用于搜索和排序的算法,每种算法都有不同的时间复杂度,但上面的示例可能会启发您如何完成这个概念. 访问网络以获取更多信息,例如https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/amp/