科学知识：时间复杂性计算方法

1。定义

（1）如果问题的大小是n，那么解决这个问题所需要的时间是t（n）。它是n，t（n）的函数，称之为算法的时间复杂度，我们使用时间复杂度的O表示法，称为奥克利方法。

（2）问题本身也有其复杂性。如果算法的复杂度达到问题复杂度的下限，我们称这种算法为最佳算法：

O（1）O（logN）<<恒阶对数阶O（N）的线性顺序< < O（nlogn）< O（n ^ 2）为O（N ^广场< 3）＜O）。

二是时间复杂度的计算过程

找出语句中的基本算法；

算法中执行次数最多的语句是基本语句，通常是最内部循环的循环。

计算语句执行时间的基本级别；

我们只需要计算基本句子执行次数，这就意味着只要保证基本句子的最高功率，就可以忽略所有的低功率和最高功率的系数，这可以简化算法分析，并把重点放在最重要的一点上：增长率。

大制作马克说算法的时间性能。

标志生产中大量订单的基本表述。

如果算法包含嵌套循环，基本语句通常是最内层循环体。如果该算法包含一个并行循环，则将增加并行循环的时间复杂度。

三，时间复杂度计算规则

（1）对于一些简单的输入输出语句或赋值语句，假定O（1）时间是必需的。

（2）对于连续结构，依次执行一系列语句所需的时间可以在大O下的和规则中使用。

求和规则：如果算法的2部分时间复杂度是T1（n）＝O（f（n））和T2（n）＝O（g（n）），则t1（n））。

特别是，如果T1（m）＝O（f（m）），T2（n）＝o（g（n）），则t1（m）。

（3）用于选择结构（如if语句）的主要时间是执行时间或语句。还需要测试条件，需要O（1）时间。

（4）对于循环结构，循环语句的运行时间主要体现在执行循环的耗时和在许多迭代中检查循环条件。乘法规则可用于大O。

乘法法则：如果算法的2部分时间复杂度是T1（n）＝O（f（n））和T2（n）＝o（g（n）），那么t1 * o＝o（f）是相同的。

（5）对于复杂算法，可分为几个容易估计的部分。然后利用求和规则和乘法规则设计整个算法的时间复杂度。