时间戳

首页 > 解决方案 > 如何计算算法的复杂度？

java - 如何计算算法的复杂度？

问题描述

int sum = 0;
for (int n = N; n > 0; n /= 2)
    for(int i = 0; i < n; i++)
        sum++;


int sum = 0;
for (int i = 1 i < N; i *= 2)
    for (int j = 0; j < i; j++)
         sum++;

int sum = 0;
for (int i = 1 i < N; i *= 2)
    for (int j = 0; j < N; j++)
        sum++;

我已经为此痛苦了很长时间。我仍然是一名二年级学生，但我仍然无法计算算法的复杂性。我该如何计算呢？我觉得自己很无能，因为我似乎从来没有得到它！

例如，for 循环的复杂度总是 N 吗？怎么知道？你能推荐任何我可以阅读的资源吗？有视频吗？

标签： javaalgorithmdata-structurestime-complexity

解决方案

那么您的第一个和第二个示例是相同的（就时间复杂度而言）。对于他们来说，时间复杂度是 O(N)。为什么。让我们计算一下。对于第一个示例，您的内部循环运行 N 次，然后是 N/2 次，然后是 N/4 并上升到 1。因此，时间复杂度为 O(N+N/2+N/4+..+1 ) 并且这个 GP 的总和是 (2n-1)。因此，第一种情况的时间复杂度为O(N)。

对于第二个示例，您的内部循环运行 1 次，然后运行 ​​2 次、4 次，然后上升到 N。因此，时间复杂度为 O(1+2+4+...+N) 和此 GP 的总和是 2 log(N+1) -1 等于 N。因此，第二种情况的时间复杂度也是O(N)。

对于第三个示例，第一个循环运行 log(N) 时间，内部循环运行 N 时间，并且由于它们中的每一个都是独立的，因此所需的时间复杂度为O(NlogN)。（所有计算均为近似值，所有对数基数均为 2）

好吧，要了解 for 循环的时间复杂度，您必须查看为“i”分配了多少次值（可以相同或不同）。

要了解时间复杂度，请查看hackerearth 资料，每次编写算法时，尝试计算其时间复杂度。它是学习它并检查 Masters theorem 的递归关系的最佳方法，但也知道它的基本原理。

推荐阅读