目录
时间复杂性
⼤O的渐进表⽰法
定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。
时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？
所以时间复杂度只能粗估，不能用来精确的进行计算
我们看一个实例：
根据上述公式
我们可以得出示例：
T(N)=N^2+2N+10
在N取不同值时，时间复杂度的粗估值也不同
时间复杂的经典实例：
实例1
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
实例二
void Func3(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);
}
实例3：
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
实例4：
const char * strchr ( const char
* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '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;
}
}')
return NULL;
p_begin++;
}
return p_begin;
}
实例5：
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
实例6
⼤O的渐进表⽰法
实例7
规则：
各位不妨自行根据规则来对将T(N)改成O(N)
答案：FUNT1:O(N)
FUNT2:O(N)
FUNT3:O(1)
FUNT6:O(logn)
FUNT7:O(n)