As the experience of using computers increases, people will inevitably ask questions like this when using computers to write programs:

How long does it take for my program to run?
Can my code be optimized to be faster and more space efficient?

When we open a web page or transfer a file or open a player, you must have asked yourself the above questions. But estimating the time and data processing complexity in this case is too difficult and vague. Compared to this large application, what we can handle is the complexity and efficiency of a single program. If the efficiency of each program is relatively good, then we don't need to worry that the final combined application will be too bloated and slow. This article will explain the algorithmic space-time complexity of the program, optimization methods and all the trivial matters. Starting from the two examples of 3-sum and 2-sum, it will demonstrate from beginning to end how the algorithm works on our program. .

Example: 3-sum and 2-sum calculation

##3-sum There are many non-repeating
integers in a file. Any three integers can form a group. Count the number of groups in which the sum of any three integers is 0.
2-sum
There are many non-repeating integers in a file. Count the number of integer pairs in which the sum of
is 0.
Brute force algorithm (conventional unoptimized algorithm):

  public int threeSum(int[] arr) {
        int count = 0;
        int n = arr.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (arr[i] + arr[j] + arr[k] == 0)
                        count++;
        return count;
    }

Copy after login

<p style="margin-bottom: 7px;">  public int twoSum(int[] arr) {<br/>        int count = 0;<br/>        int n = arr.length;<br/>        for (int i = 0; i < n; i++)<br/>            for (int j = i + 1; j < n; j++)<br/>                if (arr[i] == -arr[j])<br/>                    count++;<br/>        return count;<br/>    }<br/></p>

Copy after login

Cost

Model##If we If you want to optimize this program, you must first know where the program can be optimized. This is the

Evaluation Cost Model

. The basic operations in the algorithms we study are defined by determining the cost model of the program.

3-sum problem cost model

When studying the algorithm to solve the 3-sum problem, what we record is the number of accesses to the array
(number of accesses to the array, regardless of reading and writing)Change In short, our goal is to make the cost model we evaluate as good as possible. The model in the 3-sum problem is relatively simple, but the cost model of some complex programs needs to be determined carefully, because if we ignore some operations, the final optimization result may not be the optimal situation of the overall program.

Optimize the program based on the cost model

The violent code above does not have any problems with the results, and it is not executed well when there is less data. It's too slow. But if the amount of test data is 10 to the nth power, then this unoptimized code will have a great negative impact on time. We say that violent code is slow, but what kind of code is fast?

We have determined in the 3-sum cost model that the number of accesses to the array is what we want to study and optimize. In java, the time consumed by accessing an array is

constant

level (constant level means that it consumes almost no time). So when the time to access the contents of the array is fixed, to reduce the number of accesses to the array, we only need to make the code running time faster. In order to make code faster, we first need to understand the concepts of classification and time complexity that increase by orders of magnitude.

Order of Growth/Time Complexity

What we want to talk about is time complexity, but we changed its name to it-Order of Growth. Except for not using the big O mark, there is no difference between the two in other places. We use several structural primitives

when implementing the algorithm, such as ordinary statements,

loops

, conditional judgments, nested statements, etc., so The order of magnitude of the cost increase is generally a function of the problem size N. The problem size N in this example is the number of numbers in the array. There are seven main types of growth/time complexity:

Constant level

Order of growth : 1

Time complexity: O(1)
Typical code:

a = b + c;

Copy after login

Structural primitives: Ordinary statements

Example:Add two numbers
Explanation:The time required for a program whose running time increases by a constant order of magnitude to complete its task is Fixed, independent of N. Almost all operations in Java take constant time. Constant level speed is the fastest of all time complexities.
Logarithmic level

Order of growth: logN

Time complexity: O(logN)
Typical code:

public static int rank(int key, int[] a, int lo, int hi) {
        if (hi < lo)
            return -1;
        int mi = lo + (hi - lo) / 2;
        if (key < a[mi])
            return rank(key, a, lo, mi - 1);
        else if (key > a[mi])
            return rank(key, a, mi + 1, hi);
        else
            return mi;
    }

Copy after login

结构性原语：二分策略
举例：二分查找
说明：速度稍微慢于常数级别，但快于O(N)最典型的对数级别的例子就是二分查找，log下面的底数可能是变化的，但是因为只是一个常数对整体和N的影响不大，所以我们一般表示成logN的形式。

线性级别

增长的数量级： N
时间复杂度： O(N)
典型代码：

for (int i = 0; i < n; i++)
        if(arr[i] == 0)
            count++;

Copy after login

结构性原语： 一层循环
举例： 找出最大元素
说明： 线性级别稍慢于对数级别，但快于线性对数级别。他的运行时间和N成正比。在有些情况下，我们只需要进行一半的数组遍历，理论上可以将时间除以2，但是仍旧与N的一次方有关，所以我们把此类都算作线性级别。

线性对数级别

增长的数量级： NlogN
时间复杂度： O(NlogN)
典型代码：
归并排序
结构性原语： 分治
举例： 归并排序
说明： 线性N乘以对数logN，速度快于N²但是慢于线性级别。在归并排序中，按照类似二分的方法确定归并点，对归并到最底层的数据进行复杂度为O(N)的排序，时间复杂度为O(NlogN)。快速排序，归并排序都可以看作是线性对数级别。

平方级别

增长的数量级： N²
时间复杂度： O(N²)
典型代码：

for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (arr[i] == -arr[j])
                    count++;

Copy after login

结构性原语：双层循环
举例：检查所有元素对
说明：平方级别的程序一般都是含有两个for循环，初级的排序算法选择排序和插入排序都是这种复杂度。

立方级别

增长的数量级： N³
时间复杂度： O(N³)
典型代码：

for (int i = 0; i < n; i++)  for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            if (arr[i] + arr[j] + arr[k] == 0)
                count++;

Copy after login

结构性原语：三层循环
举例：对数组中的三个数据进行操作
说明：立方级别的代码一般都是三个for循环嵌套而成，我们日常的算法很少有这种运算时长。

指数级别

增长的数量级： 2^N
时间复杂度： O(2^N)
典型代码：
穷举查找所有真子集
结构性原语：穷举法
举例：穷举查找所有真子集
说明：指数级别的增长在N较大时比较可怕，但是它确是某些问题看起来最优的解法，并不是很常用，等如果需要学习的时候可以专门研究。

优化2-sum问题

先从2-sum问题入手，根据上述复杂度，2-sum问题的暴力解法复杂度为O(N²)，又根据我们的成本模型只考虑访问数组次数，所以我们要在O(N²)的复杂度之内寻求最优解法即可。

从上面得知，排序算法的复杂度是O(NlogN)快于O(N²)，而我们对排序之后的数据进行运算时，已经不是在排序内部进行处理。所以最后计算时间是用加法而不是乘法。所以我们最后的解决策略是：我们先对整个数组进行排序，然后从数组头部依次读取a[i]，在数组中检索是否存在-a[i]。这种检索采用了二分查找的方法，复杂度为O(logN)。为了避免重复查找，如果查找到-a[i]的位置在a[i]之前，就说明该元素对已经被查找过，不计入次数。这样整体的算法复杂度是NlogN+N*logN（不知道这样写是否规范）。两项合并系数忽略，所以最后算法整体的复杂度为O(NlogN)。

public int twoSum(int[] arr) {
        int count = 0;
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++)
            if (Arrays.binarySearch(arr, -arr[i]) > i)
                count++;
        return count;
    }

Copy after login

2-sum问题已经成功的进行了优化，3-sum问题也可以通过这种方式进行优化，但是最后优化的复杂度为O(N²logN)，感兴趣的朋友可以自己试一试，或者有更简便算法的话，发在评论里我们交流一下。不胜感激。

Notes on optimizing optimization algorithms

Large constant

In the first approximation, We generally ignore constant coefficients in low-level terms, but this may be wrong. For example, when we approximate the function 2N²+cN to ~ 2N², our assumption is that c is small. But if c might be a very high power of 10, the approximation is wrong. We need to be sensitive to constants that may be large.

Wrong Cost Model

The assumption that the inner loop is the decisive factor is not always correct. An incorrect cost model may fail to obtain the true inner loop, or may not pay enough attention to certain statements in the loop, resulting in errors in time estimation. All in all, the cost model needs improvement.

The above is the detailed content of Detailed explanation of algorithms and optimization methods for Java time calculation. For more information, please follow other related articles on the PHP Chinese website!