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

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

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

로그인 후 복사

rrree

비용모델

We If 이 프로그램을 최적화하려면 먼저 프로그램을 어디에서 최적화할 수 있는지 알아야 합니다. 이것이

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

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

교체 간단히 말해서 우리의 목표는 우리가 평가하는 비용 모델을 최대한 좋게 만드는 것입니다. 3합 문제의 모델은 상대적으로 간단하지만 일부 복잡한 프로그램의 비용 모델은 신중하게 결정해야 합니다. 왜냐하면 일부 작업을 무시하면 최종 최적화 결과가 전체 프로그램의 최적 상황이 아닐 수 있기 때문입니다.

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

위의 폭력적인 코드는 결과에 문제가 없으며, 데이터가 너무 적어요. 그러나 테스트 데이터의 양이 10의 n승이라면 이 최적화되지 않은 코드는 시간에 큰 부정적인 영향을 미칠 것입니다. 폭력적인 코드는 느리다고 하는데 어떤 코드가 빠른가요?

우리는 어레이에 대한 액세스 횟수가 3-sum 비용 모델에서 연구하고 최적화하려는 횟수라고 판단했습니다. Java에서는 배열에 액세스하는 데 소요되는 시간이

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

성장 순서/시간 복잡도

우리가 이야기할 것은 시간 복잡도이지만, 성장 순서라는 다른 이름을 붙였습니다. 큰 O 표시를 사용하지 않은 것 외에는 다른 곳과 별 차이가 없습니다. 우리는 알고리즘을 구현할 때 일반 명령문,

루프, 조건 판단, 중첩 명령문 등 여러 가지 구조적 기본 요소를 사용했습니다. 비용 증가는 일반적으로 문제 크기 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;
    }

로그인 후 복사

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

최적화 알고리즘 최적화에 대한 참고 사항

큰 상수

첫 번째 항 근사에서 우리는 일반적으로 낮은 수준의 상수 계수는 무시하지만 이는 잘못된 것일 수 있습니다. 예를 들어 함수 2N²+cN을 ~ 2N²으로 근사할 때 c가 작다고 가정합니다. 그러나 c가 10의 매우 높은 거듭제곱일 수 있다면 근사치는 잘못된 것입니다. 우리는 클 수 있는 상수에 민감해야 합니다.

잘못된 비용 모델

내부 루프가 결정적인 요소라는 가정이 항상 올바른 것은 아닙니다. 잘못된 비용 모델은 실제 내부 루프를 얻지 못하거나 루프의 특정 설명에 충분한 주의를 기울이지 않아 시간 추정 오류가 발생할 수 있습니다. 전체적으로 비용 모델의 개선이 필요합니다.

위 내용은 Java 시간 계산을 위한 알고리즘 및 최적화 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!