单页简洁手机网站模板,购物软件,360免费网站空间,广州市第一建筑工程有限公司目录
时间复杂性
⼤O的渐进表⽰法 时间复杂性
定义#xff1a;在计算机科学中#xff0c;算法的时间复杂度是⼀个函数式T(N)#xff0c;它定量描述了该算法的运⾏时间。 时间复杂度是衡量程序的时间效率#xff0c;那么为什么不去计算程序的运⾏时间呢#xff1f; 1.…目录
时间复杂性
⼤O的渐进表⽰法 时间复杂性
定义在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运⾏时间。 时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运⾏时间呢 1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系⽐如同⼀个算法程序⽤⼀个⽼编译 器进⾏编译和新编译器编译在同样机器下运⾏时间不同。 2. 同⼀个算法程序⽤⼀个⽼低配置机器和新⾼配置机器运⾏时间也不同。 3. 并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。 所以时间复杂度只能粗估不能用来精确的进行计算 我们看一个实例 // 请计算⼀下Func1中count语句总共执⾏了多少 次 void Func1(int N) { int count 0; for (int i 0; i N; i) { for (int j 0; j N; j) { count; } } for (int k 0; k 2 * N; k) { count; } int M 10; while (M--) { count; } } 时间复杂度计算公式每条语句的运行时间不确定*语句运行次数确定 根据上述公式
我们可以得出示例 T(N)N^22N10 在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 \0)
return NULL;
p_begin;
}
return p_begin;
} 实例5
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;
}
} 实例6
void func5(int n)
{
int cnt 1;
while (cnt n)
{
cnt * 2;
}
} 实例7 ⼤O的渐进表⽰法
规则 1.时间复杂度函数式T(N)中只保留最⾼阶项去掉那些低阶项因为当N不断变⼤时 低阶项对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。 2. 如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数 对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。 3. T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。 各位不妨自行根据规则来对将T(N)改成O(N)
答案FUNT1:O(N)
FUNT2:O(N)
FUNT3:O(1) FUNT4: 1.O(1) 2.O(N) 3.O(N) FUNT5: 1.O(1) 2.O(N^2) FUNT6:O(logn)
FUNT7:O(n)
