【每日阅读】2021年04月27日-时间复杂度示例

真诚的希望您能留言与我交流,这会对我有非常大的帮助!

O(1)

int i = 8;
int j = 6;
int sum = i + j;

O(logn)、O(nlogn)

i=1;
while (i <= n)  {
    i = i * 2;
}

上面算法的时间复杂度是O(logn),如果循环n次就成了O(nlogn)

i=1;
while (i <= n)  {
    i = i * 3;
}

上面算法也是O(logn),因为对数之间是可以相互转换的,都可以转换成以2为底的对数,所以说时间复杂度时忽略底数,直接说logn

O(m+n)、O(m*n)

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

上面的是O(m+n),因为两部分分别执行m次和n次。

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/2978

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

GitHub
分享本页
返回顶部