컴퓨터 사용 경험이 늘어남에 따라 사람들은 컴퓨터를 사용하여 프로그램을 작성할 때 필연적으로 다음과 같은 질문을 받게 됩니다.

내 프로그램이 실행되는 데 얼마나 걸리나요?
내 코드를 더 빠르고 공간 효율적으로 최적화할 수 있나요?

우리가 웹페이지를 열거나 파일을 전송하거나 플레이어를 열 때 위와 같은 질문을 스스로에게 물어보셨을 것입니다. 그러나 이 경우 시간과 데이터 처리 복잡성을 추정하는 것은 너무 어렵고 모호합니다. 이 대규모 애플리케이션에 비해 우리가 처리할 수 있는 것은 단일 프로그램의 복잡성과 효율성입니다. 각 프로그램의 효율성이 상대적으로 좋다면 최종 결합된 애플리케이션이 너무 비대해지고 느려지는 것을 걱정할 필요가 없습니다. 이 기사에서는 프로그램의 알고리즘 시공간 복잡성, 최적화 방법 및 모든 사소한 문제를 3-sum과 2-sum의 두 가지 예에서 시작하여 우리 프로그램에서 알고리즘이 어떻게 작동하는지 처음부터 끝까지 보여줍니다. .

예: 3합 및 2합 계산

3합
파일에 반복되지 않는 정수가 많이 있습니다. 임의의 세 정수가 그룹을 형성할 수 있습니다. 세 정수의 합이 0인 그룹의 수를 세어보세요.

2섬 파일에 반복되지 않는 정수가 많이 있습니다.
의 합이 0인 정수 쌍 의 수를 계산합니다.

  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;
    }

비용모델

평가 비용 모델입니다. 우리가 연구하는 알고리즘의 기본 작업은 프로그램의 비용 모델을 결정하여 정의됩니다.

3합 문제의 비용 모델 3합 문제를 풀기 위한 알고리즘을 연구할 때 우리가 기록하는 것은
배열 의 액세스 횟수(읽기와 쓰기에 관계없이 배열에 대한 액세스 횟수)입니다.

비용 모델을 기준으로 프로그램 최적화

일정 수준입니다(일정 수준은 시간을 거의 소비하지 않는다는 의미). 따라서 배열의 내용에 접근하는 시간이 고정되어 있을 때, 배열에 대한 접근 횟수를 줄이기 위해서는 코드 실행 시간을 더 빠르게 만들기만 하면 됩니다. 코드를 더 빠르게 만들기 위해서는 먼저 분류의 개념과 수십 배로 증가하는 시간 복잡도를 이해해야 합니다.

성장 순서/시간 복잡도

루프, 조건 판단, 중첩 명령문 등 여러 가지 구조적 기본 요소를 사용했습니다. 비용 증가는 일반적으로 문제 크기 N의 함수입니다. 이 예에서 문제 크기 N은 배열의 숫자 수입니다. 크기/시간 복잡도에는 7가지 주요 유형이 있습니다.

상수 수준

1 시간 복잡도:
O(1) 일반 코드:

<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>

일반적인 문장예:
두 숫자 더하기설명:
실행 시간이 몇 배나 증가하는 프로그램이 일정하게 완료되는 데 걸리는 시간 해당 작업은 N과 독립적으로 고정되어 있습니다. Java의 거의 모든 작업에는 일정한 시간이 걸립니다. 일정한 수준의 속도는 모든 시간 복잡도 중에서 가장 빠릅니다.

로그 수준

logN 시간 복잡도:
O (logN) 일반적인 코드:

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;
    }

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

线性级别

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

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

结构性原语： 一层循环
举例： 找出最大元素
说明： 线性级别稍慢于对数级别，但快于线性对数级别。他的运行时间和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++;

结构性原语：双层循环
举例：检查所有元素对
说明：平方级别的程序一般都是含有两个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++;

结构性原语：三层循环
举例：对数组中的三个数据进行操作
说明：立方级别的代码一般都是三个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;
    }