时间复杂度计算

目录

时间复杂性

⼤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^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 == '\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)