在工作空间里,在笛卡尔空间想去哪就去哪。
拖动示教能不能想拖哪里就拖哪里
现在我们就大概明白了如何来计算一个算法的时间复杂度,下面我们来看几个代码练习一下。
void Func(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}
for (int k = 0; k < N; ++k)
{
++count;
}
printf("%d\n", count);
}
在这个算法中,我们在传入了两个变量,导致两个循环的循环次数分别由两个变量来决定,这时我们认为时间复杂度为O(N+M),因为我们不知道M和N谁大,所以我们谁都无法省略。
void my_strchr(char* str,char c)
{
while (*str != '\0')
{
if (*str == c)
{
return str;
}
str++;
}
}
这是一个简单的字符串查找函数,在这个算法中,并没有一个变量值来描述我们需要进行循环的次数,而觉得我们循环次数的是被查找字符串的长度,在时间复杂度的计算中,我们通常假设数组或字符串的长度为N,还有一个问题是这个算法中即使我们知道了字符串的长度但是我们执行循环的次数也是不一定的,因为我们不知道什么时候能够在字符串中找到我们寻找的元素,可能我们在第一个位置就找到了,也有可能我们要遍历整个字符串在最后一个元素的位置才能找到,出现这种情况时默认时间复杂度要以最坏的情况为准,即O(N)。
冒泡排序的时间复杂度?
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
上面的是一个冒泡排序的函数,我们知道在进行冒泡排序时,我们首先要进行N次排序,然后在每次排序时,我们又要遍历这个数组,但是我们每进行一次排序,在下一次排序时我们就可以少遍历一个元素,所以我们可以得到实际的运算次数F(N)=N+(N-1)+(N-2)……+2+1。这是一个等差数列,结果化简为F(N)=N*(N+1)/2,所以时间复杂度为O(N²)
二分查找的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
上面的是一个二分查找函数的代码,我们知道二分查找是在一个有序数组中查找某一个元素时的比较高效的方法,在进行二分查找时,我们每次都取数组的中间值,然后再根据中间值与查找值的大小来确定我们要查找的元素在那一半,然后在对找到的哪一半数组进行重复的操作,直到找到我们需要的元素,使用二分查找时,最坏的情况是我们把数组除的只剩最后一个元素,这时表达式为N÷2÷2÷2÷2…÷2÷2=1我们把这个式子换算一下为
N=1×2×2×2…×2×2我们每相乘一次,就进行了一次基本操作,所以上式中我们一共进行了log₂N次,所以时间复杂度为O(log₂N)。
递归的时间复杂度?
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}
上面的代码是一个计算斐波那契数列的函数,使用的是递归的方法,我们知道递归的方法来计算斐波那契数列是非常低效的,最好还是使用循环的方法,但是递归的时间复杂度是多少呢?
我们知道每一次调用这个函数时,我们的时间复杂度是一个常数,那么这个递归的时间复杂度就是我们一共调用了多少次函数,现在我们来分析一下我们到底调用了多少次这个函数。
其调用结构如图所示
当我们输入N时,函数会进行两调用,然后不断地调用,其调用的结果如图所示,在右下角是有一个空缺区域的,但是我们可以把这一块空缺的区域看作一个常数,假设它是满的,那么我们执行调用的总次数为F(N)=2⁰+2¹+2²+…+2N-1=2N-1,所以该算法的时间按复杂度为O(2N)。
由以上的计算我们就可以发现用递归来算斐波那契数的算法的时间复杂度太高了,也就说明了这个算法的低效。