int cal(int n)
{
int sum = 0;
int i = 1;
for (; i <= n; ++i)
{
sum = sum + i;
}
return sum;
}
以查找为例,看如下代码
// n 表示数组 array 的长度
int find(int[] array, int n, int x)
{
int i = 0;
int pos = -1;
for (; i < n; ++i)
{
if (array[i] == x)
{
pos = i;
break;
}
}
return pos;
}
最好情况时间复杂度就是在程序最理想的状态下,数组第一个元素就是我们要查找的元素,只需要查找一次;而最坏情况时间复杂度就是在程序最糟糕的状态下,数组最后一个元素才是我们要查找的元素,需要查找完整个数组;
事实上,我们要查找的元素可能存在数组中的任何一个位置,甚至可能不存在于数组中,因此,考虑所有情况出现的概率,求出各种情况下时间复杂度的平均值,也就是平均情况时间复杂度。
// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val)
{
if (count == array.length)
{
int sum = 0;
for (int i = 0; i < array.length; ++i)
{
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
这段代码的功能是向数组中插入一个元素,当数组未满时,直接插入,时间复杂度为O(1);当数组满时,先计算数组所有元素的和,再插入元素,时间复杂度为 O(n)。
并且,两种复杂度不同的操作具有一定的规律,一系列O(1)的插入导致数组占满,然后紧跟着一个O(n) 的插入,再继续循环往复。
这时候,我么就可以把O(n) 复杂度的这个操作平均分摊到前面的O(1)复杂度操作上去,整体的时间复杂度也就变成了O(1),这就是均摊情况时间复杂度。
如果大部分情况时间复杂度都很低,只有少数情况时间复杂度较高,并且这些操作具有前后的时序关系,那么我们就可以应用均摊情况时间复杂度来进行分析。通常来说,均摊情况时间复杂度就等于最好情况时间复杂度。
称为与f(n)同阶的函数集合。
称为比 f(n)低阶的函数集合。
称为比f(n)高阶的函数集合。
称为f(n)的严格低阶函数集合。
称为比f(n)高阶的函数集合。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。