学习数据结构和算法的第3天

常数循环的复杂度

计算Func4的时间复杂度

voidFunc4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}

O（1） 不是代表算法运行一次，是常数次

strchar的时间复杂度

#include<stdio.h>
void const char*strchr(const char*str,int character);
{while(*str){if(*str==character)return 0;else++str;}
}

假设查找的是h 1 最好情况：任意输入规模的最小运行次数(下界)

假设查找的是w N/2 平均情况：任意输入规模的期望运行次数

假设查找的是d N 最坏情况：任意输入规模的最大运行次数(上界)

当一个算法随着输入不同，时间复杂度不同，时间复杂度做悲观预期，看最坏的情况

冒泡排序的时间复杂度

计算Bubb1esort的时间复杂度

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; ++1){if (a[1-1]> a[i]){Swap(&a[1-1], &a[i]);exchange = 1;}}if (exchange == 0)
break;}
}

精确：F(N）=N（N-1)/2* 一个等差数列

时间复杂度：O（N*2)

时间复杂度不能只看是几层循环，而是要去看它的思想

计算Binarysearch的时间复杂度:

int Binarysearch(int* a, int n, int x)
{assert(a);int begin= 0;int end = nl;while (begin < end){int mid = begin + ((end-begin)>>1);if (a[mid] < x)begin = mid+1;else if (a[mid] > x)end=mid;elsereturn mid;}
return -1;
}

F(N)=O(logN)