针对于数据结构,算法便是操作数据结构的方法,为了更好的评判算法运行时间长短,需要有合适的方法即算法时间复杂度这一概念来进行估算.

分析方法

  • 关注随着”n”变化的且运行次数最多的执行语句,此语句的时间复杂度则是该算法的时间复杂度.
  1. int cal(int n) {
  2.     int sum = 0;
  3.     int i = 1;
  4.     for (; i <= n; ++i) {
  5.         //关注这一语句的时间复杂度即可
  6.          sum = sum + i;
  7.     }
  8.     return sum;
  9. }
  • 加法法则:如果两个未知量m&n,没有嵌套的情况,那么选择m和n之间较大的那个数的时间复杂度.
  • 乘法法则:如果两个未知量m&n,形成了嵌套的语句,那么时间复杂度便是O(m)*O(n).
  • 没有因为n而导致执行次数变化的语句,则其时间复杂度便是O(1).

  • 所有对数相关的时间复杂度都是log为底

    1. i=1;
    2. while (i <= n) {
    3.    //时间复杂度为log(n), 因为2^0,  2^1, 2^2,  ......,  2^j = n得到 2^j = n,得到j的值为log2(n),即循环执行了j次.
    4.    i = i * 2;
    5. }

  • 同时出现m和n以及其他的未知数,但是不知他们之间的大小则时间复杂度为O(m+n)

    极端情况:最好时间复杂度&最坏时间复杂度

    这个只需要找到最好的情况和最坏的情况直接估计即可

    平均时间复杂度的计算方法

    平均时间复杂度即考虑所有会出现的情况,其计算公式如下:

如何计算算法的时间复杂度 - 图1

空间复杂度

空间复杂度与时间复杂度相似.

  • 时间复杂度关注语句执行次数.
  • 空间复杂度关注变量存储空间,如申请内存地址的次数.