알고리즘의 품질을 평가하는 방법

첫째, 이 알고리즘은 정확해야 합니다.

둘째, 좋은 알고리즘은 친숙하고, 사람들이 이해하고 의사소통하기 쉽고, 기계에서 실행 가능해야 합니다.

이 알고리즘은 또한 충분히 강력해야 합니다. 즉, 입력 데이터가 불법이거나 불합리한 경우 적절하게 대응하거나 그에 따라 처리할 수 있어야 합니다.

마지막으로 효율성이 높고 저장 요구 사항이 낮아야 합니다. +                                            정의: 컴퓨터 과학에서 알고리즘의 시간 복잡도는 알고리즘의 실행 시간을 정량적으로 설명하는 함수입니다. 이론적으로 알고리즘을 실행하는 데 걸리는 시간은 프로그램을 컴퓨터에 올려놓아야 알 수 있습니다. 그러나 알고리즘을 결정하는 데 걸리는 시간은 기본 작업 실행 횟수에 비례합니다. 알고리즘은 알고리즘의 시간 복잡도입니다.

2. 시간 복잡도는 왜 시간이 아닌 기본 명령문의 실행 횟수로 측정됩니까?

알고리즘의 실행 시간은 특정 소프트웨어 및 하드웨어 환경에 따라 다릅니다. 따라서 알고리즘의 시간 복잡도는 실행 시간의 길이로 측정할 수 없으며 기본 명령문 실행 횟수의 크기로 측정됩니다.

3. 시간 복잡도의 O 점근 표기법(Big O 표기법)

은 함수의 점근적 동작을 설명하는 데 사용되는 수학적 기호입니다.

Big O 순서 방법 파생:

크기 순서를 계산합니다.

기본문 실행 횟수의 크기만 계산하면 됩니다. 이는 기본문 실행 횟수의 함수에서 가장 높은 전력을 의미합니다. 진술이 정확하면 낮은 거듭제곱과 가장 높은 거듭제곱의 모든 계수를 무시할 수 있습니다. 이는 알고리즘 분석을 단순화하고 가장 중요한 점인 성장률에 주의를 집중시킵니다. 알고리즘에 중첩 루프가 포함된 경우 기본 문은 일반적으로 가장 안쪽 루프 본문입니다. 알고리즘에 병렬 루프가 포함되어 있으면 병렬 루프의 시간 복잡도가 추가됩니다. 예:

　for (i=1; i 첫 번째 for 루프의 시간 복잡도는 Ο(n)이고 두 번째 for 루프의 시간 복잡도는 Ο(n2)이며 전체 알고리즘의 시간 복잡도는 Ο(n+n2)=입니다. Ο(n2). <p></p><p> 4. 시간 복잡도: 최적, 평균, 최악의 경우. 시간 복잡도는 왜 최악의 경우로 보나요? <br><br><br> 최악의 복잡성은 가능한 모든 입력 데이터가 소비하는 최대 리소스입니다. 최악의 복잡성이 요구 사항을 충족하는 경우 모든 경우에 문제가 없음을 보장할 수 있습니다. </p><p> 일부 알고리즘은 종종 최악의 시나리오에 직면합니다. 예를 들어, 검색 알고리즘은 종종 존재하지 않는 값을 찾아야 합니다. </p> 어쩌면 당신은 평균적인 사례의 복잡성이 더 매력적이라고 ​​생각할 수도 있지만, 평균적인 사례에는 몇 가지 문제가 있습니다. 첫째, 대부분의 알고리즘의 최악의 경우 복잡도는 평균의 경우보다 계산하기가 훨씬 쉽습니다. 둘째, 많은 알고리즘의 평균 경우와 최악의 경우 복잡도가 동일합니다. 셋째, 사실은 무엇입니까? 평균? 가능한 모든 입력 데이터가 동일한 발생 확률을 갖는다고 가정하는 것도 불합리합니다. 실제로 대부분의 상황은 다릅니다. 그리고 입력 데이터의 분포 함수는 아마도 당신이 알 수 없는 것일 것입니다. <p>최상의 시나리오의 복잡성을 고려하는 것은 의미가 없습니다. <strong></strong></p> 5. 해결 방법: 이진 검색, 재귀 계승 및 재귀 피보나치의 시간 복잡도? <p></p><p> 이진 검색: 종이접기 검색을 통해 해결하는 시간 복잡도는 O(logN)입니다. <br> 재귀 계승 계산: 기본 연산을 N 번 반복하여 O(N)의 시간 복잡도를 얻습니다. <br> 재귀 피보나치: 분석 결과 기본 연산은 2</p>N회 재귀적이며, 시간복잡도는 O(2<p>N)입니다.<strong></strong></p> 6. 공간복잡도란 무엇인가요? <p><br><br> 공간 복잡도는 알고리즘이 작업 중에 일시적으로 차지하는 저장 공간의 양을 측정한 것입니다. 공간 복잡도는 프로그램이 차지하는 공간의 바이트 수는 의미가 없으므로 공간 복잡도는 변수로 계산됩니다. . 공간 복잡도 계산 규칙은 기본적으로 시간 복잡도와 유사하며 Big O 점근법을 사용하여 표현됩니다.<sup><p><strong>    7.如何求空间复杂度？ 普通函数&递归函数</strong></p>
<p style="line-height: 2em;">    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为 递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。</p>
<p style="line-height: 2em;"><strong>    8. 分析递归斐波那契数列的：时间、空间复杂度，并对其进行优化，伪递归优化—>循环优化</strong></p>
<pre class="brush:php;toolbar:false">long long Fib(int N) {
	if (N <p>    普通递归实现的斐波那契数列:<br>    时间复杂度:O(2^n)<br><img src="https://img.php.cn/upload/article/000/000/051/79601e8681a1e563f3ddfcadebcb758c-0.png" alt="알고리즘의 품질을 평가하는 방법"><br>    计算并根据<strong>O渐进表示法</strong>得出时间复杂度.</p><p>    空间复杂度:O(N);递归深度乘以(每一次递归的空间占用{有辅助空间或常量})</p><p>    伪递归优化:</p><pre class="brush:php;toolbar:false">long long fib (long long first, longlong second, int N) {
	if(N <p>    时间复杂度:<br>    O(N);<br>    递归深度乘以每次递归的循环次数<br>    空间复杂度:<br>    O(1)或O(N)<br>    关键看编译器是否优化,优化则为O(1)否则O(N);</p><p>    循环优化:</p><pre class="brush:php;toolbar:false">long long  Fib(int N) {
	long long first = 1;
	long long second = 1;
	long long ret = 0;
	
	for (int i = 3; i <p>    时间复杂度:O(N);</p><p>    空间复杂度:O(1);</p><p>    <strong>9.常见时间复杂度</strong></p><p>    常见的算法时间复杂度由小到大依次为：　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。</p><link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-60ecaf1f42.css" rel="stylesheet"><!-- flowchart 箭头图标 勿删 --><svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path></svg>

위 내용은 알고리즘의 품질을 평가하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!