프로그램 시간 복잡성을 줄이기 위해 PHP에서 배열을 영리하게 사용

시간 복잡도는 개발자가 애플리케이션 알고리즘의 장점을 측정하는 데 사용하는 주요 요소입니다. 객관적으로 말하면, 알고리즘의 품질은 시간 복잡도뿐만 아니라 공간 복잡도와도 밀접한 관련이 있습니다. 장치 하드웨어 구성이 지속적으로 개선됨에 따라 중소 규모 애플리케이션에 대한 알고리즘의 공간 복잡성 요구 사항이 훨씬 완화되었습니다. 그러나 오늘날 Web2.0 시대에는 애플리케이션의 시간 복잡도에 대한 요구 사항이 더 높아졌습니다.

알고리즘의 시간복잡도는 얼마나 되나요? 정리하면, 알고리즘을 대표할 수 있는 알고리즘 중에서 원래의 연산을 선택하고, 원래의 연산이 반복되는 횟수를 알고리즘의 시간 측정치로 삼는 것을 말한다. 시간 복잡도에 영향을 미치는 두 가지 요소가 있습니다. 하나는 원래 작업의 실행 시간이고 다른 하나는 제어 구조로 인해 발생하는 원래 작업의 실행 횟수입니다. 알고리즘의 시간 복잡도를 줄이기 위해서는 원래 연산의 실행 횟수를 줄이는 것이 더 쉽고 주요한 방법이다. 이 기사에서 설명하는 방법은 PHP 배열을 교묘하게 사용하여 원래 작업의 실행 횟수를 줄여 알고리즘의 시간 복잡도를 줄이고 이를 모든 사람과 공유할 필요성을 달성하는 것입니다.

알고리즘의 시간 측정은 T(n)=O(f(n))으로 기록되는데, 이는 알고리즘의 기본 연산의 반복 실행 횟수가 함수 f(n)임을 의미합니다. 즉, 문제 크기 n이 커질수록 알고리즘 수행 시간의 증가율은 f(n)의 증가율과 같다고 한다. 대부분의 경우 알고리즘의 시간 복잡도를 논의하기 위해 가장 깊은 루프의 명령문을 원래 작업으로 사용합니다. 왜냐하면 명령문이 실행되는 횟수는 이를 포함하는 명령문의 빈도와 동일하기 때문입니다. 일반적으로 문제의 경우 알고리즘의 시간 복잡도를 논의하기 위해 기본 작업만 선택하면 됩니다. 때로는 여러 기본 작업을 동시에 고려해야 합니다.

웹 개발에서 일반적으로 함수의 실행 시간이나 응답 시간은 서버의 응답 능력 및 처리 능력과 관련될 뿐만 아니라 링크 시간과 같은 타사 도구의 상호 작용 시간도 포함됩니다. 데이터베이스에 대한 연결 시간 및 데이터에 액세스한 시간입니다. 따라서 원본 연산을 선택할 때에는 응용의 모든 측면을 종합적으로 고려해야 하며, 프로그램 실행 시간에 가장 큰 영향을 미치는 연산을 원본 연산으로 사용하여 알고리즘의 시간 복잡도를 측정해야 합니다. 즉, 프로그래머는 코드를 작성할 때 중요한 작업의 실행 시간에 대한 기본적인 이해가 필요합니다.

먼저 웹 프로그램의 개발 언어가 PHP이고, 백그라운드가 DB2 데이터베이스를 사용하고, PHP가 PEAR::DB 데이터 추상화 계층은 데이터베이스에 대한 액세스를 달성합니다.

데이터베이스에는 학생 테이블 STUDENTS(표 1 참조), 수업 테이블 CLASSES(표 2 참조) 및 학생 성과 테이블 SCORES(표 3 참조)가 포함되어 있습니다. 웹페이지 이번 시험에서 수학에서 90점 이상을 획득한 학생의 이름과 학급입니다.

표 1. STUDENTS 테이블

컬럼 이름 설명

SID 학생 번호

STUNAME 이름

GENDER 성별

AGE 연령

CLASSID 클래스 번호

…

표 2. CLASSES 테이블

열 이름 설명

CLASSID 클래스 번호

CLASSNAME 클래스 이름

…

표 3. SCORES 테이블

컬럼 이름 설명

SID 학생번호

COURSE 과목

SCORE Score

…

개인의 프로그래밍 습관에 따라 보통 두 가지 방법으로 이를 해결합니다. 이를 수행하는 방법(데이터베이스에 액세스하는 작업은 PEAR::DB 형식으로 표현됨), 방법 1과 2를 참조하십시오.

[방법 1] STUDENTS, CLASSES, SCORES 3개의 테이블에 대해 공동 질의를 수행하여 조건에 맞는 학생 정보와 수업 정보를 한번에 얻는다. PHP 알고리즘은 다음과 같이 설명됩니다.

$querystr = "STUNAME으로 고유한 S.STUNAME 선택, CLASSNAME으로 C.CLASSNAME ".
" from STUDENTS as S ,CLASSES는 C, SCORES는 R ".
", 여기서 S.SID=R.SID 및 S.CLASSID=C.CLASSID 및 R.COURSE='Math' ".
"및 R.SCORE>= 90";
$result = $db2handle->query( $querystr ); //데이터베이스에서 데이터 가져오기
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//읽기 그리고 데이터
를 표시합니다. echo "StudentName=".$row['STUNAME']."/t ClassName=".$row['CLASSNAME']."/n"
}//완료

[방법 2] SCORES 테이블에서 조건에 맞는 학번을 찾고, STUDENTS 테이블에서 학생 이름과 학급 코드를 찾아 최종 학급명을 얻는다. CLASSES 테이블에서. PHP 알고리즘은 다음과 같이 설명됩니다.

$scorestr = "COURSE='Math' 및 SCORE>=90인 SCORES에서 고유한 SID 선택";
$scoredata = $db2handle->query( $scorestr )//에서 가져옵니다. 조건에 맞는 데이터베이스 학생 ID 번호
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//학생 ID 번호를 읽고 STUDENTS 테이블에서 학생 이름과 학번을 찾습니다
$studentstr = "SID='".$score['SID']."'"인 STUDENTS에서 STUNAME,CLASSID를 선택합니다.
$studata =$db2handle->query( $studentstr);
$stu =$studata->fetchRow(DB_FETCHMODE_ASSOC);
//학생 이름 표시
echo "StudentName=".$stu['STUNAME']."/t ";
//학생 이름 읽기 학급 번호 및 CLASSES 테이블에서 학생의 학급 이름을 찾습니다.
$classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'";
$classdata = $ db2handle->query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//학생의 수업 표시
echo "CLASSNAME=".$class['CLASSNAME'] . "/n";
}//각 학생의 ID를 가져오는 동안 완료

이러한 알고리즘 설명은 모두가 친숙하게 느낄 것이라고 믿습니다. 이는 대부분의 프로그래머가 널리 사용하는 알고리즘이기도 합니다. 내 생각 속의 알고리즘 논리를 직접 코드로 옮기는 데 익숙해지다 보니, 알고리즘의 장단점을 생각해 볼 시간과 생각이 부족한 경우가 많습니다. 여기서는 이 두 알고리즘의 시간 복잡도를 분석합니다.

웹 서버가 데이터를 읽고 표시하는 데 걸리는 시간은 일반적으로 10ms 정도로 비교적 작기 때문에 DB2 데이터베이스에서 데이터를 쿼리하고 가져오는 데 걸리는 시간은 대략 10ms 정도입니다. 100ms이며 쿼리 데이터의 양에 따라 달라집니다. 따라서 데이터베이스를 질의하는 연산을 시간복잡도를 측정하기 위한 원본 연산으로 사용할 수 있으며, STUDENTS 테이블과 SCORES 테이블의 데이터량을 문제 크기 n으로 사용한다(보통 CLASSES 테이블의 데이터량은 작고 상대적으로 안정적입니다.)

방법 1의 경우 문제 크기 n이 커질수록 데이터베이스 액세스 횟수는 1로 일정합니다. 따라서 시간복잡도는 T(n)=O(1)이다. 방법 2의 경우 SCORES 테이블에 조건에 맞는 m개의 레코드가 있다고 가정하면 원래 연산의 실행 횟수는 m+1이 된다. 즉, 데이터 크기 n이 증가할수록 원래 연산의 실행 횟수는 선형적으로 증가한다. 시간복잡도는 T(n)=O(n)임을 알 수 있다. 방법 1의 시간 복잡도가 낮다는 것을 알 수 있다.

그럼 방법 1의 문제점은 무엇인가요? 주된 이유는 방법 1이 데이터베이스 부하를 증가시키기 때문입니다. 즉, 원래 작업의 실행 시간은 문제 크기 n에 의해 크게 영향을 받습니다. STUDENTS, CLASSES, SCORES의 레코드 수가 각각 X, Y, Z라고 가정합니다. 그런 다음 공동 쿼리 작업을 수행할 때 레코드 번호가 있는 행렬 이런 식으로 어떤 테이블의 데이터가 증가하면 PHP 배열(Array)의 첨자(Index)가 문자열(String)이 될 수 있다는 점을 활용하여 매트릭스 테이블의 레코드 수가 배가됩니다. 데이터는 영리한 방법으로 배열에 임시로 저장될 수 있습니다. 이렇게 하면 인덱스를 통해 필요한 값을 빠르게 얻을 수 있어 데이터베이스에 대한 쿼리 수를 줄여 알고리즘의 시간 복잡도를 줄일 수 있다.

[방법 3] CLASSES 테이블에서 CLASSID와 CLASSNAME의 대응 관계를 얻어 ClassArray 1차원 배열에 저장한다. STUDENTS 테이블에서 SID와 STUNAME, CLASSID의 대응 관계를 얻어 저장한다. StuArray 2차원 배열에서. 그런 다음 SCORES 테이블에서 조건에 맞는 학생 ID 번호를 찾고, StuArray 배열에서 학생 이름과 학급 번호를 읽고, ClassArray에서 학급 이름을 읽어옵니다. PHP 알고리즘은 다음과 같이 설명됩니다.

$ClassArray = Array();
$StuArray = Array();
$classstr = "클래스에서 CLASSID,CLASSNAME 선택";
$classdata = $db2handle->query( $classstr) ;
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//ClassArray 배열을 생성합니다. 첨자 Index는 CLASSID 이름을 따서 명명되고 해당 값은 CLASSNAME
$ClassArray[$ class[' CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stusr="select SID,STUNAME,CLASSID from STUDENTS";
$studata = $ db2handle-> query( $stustr);
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//StuArray 배열을 생성하고 아래 첨자 Index는 SID 이름을 따서 명명되며 해당 값 ​​STUNAME 및 CLASSID
$StuArray[$stu ['SID']]['STUNAME'] = $stu['STUNAME'];
$StuArray[$stu ['SID']]['CLASSID '] = $stu['CLASSID '];
}//end while $StuArray
$scorestr = "COURSE='Math' 및 SCORE>=90인 SCORES에서 고유한 SID 선택";
$ Scoredata = $db2handle->query( $scorestr );
//데이터베이스에서 조건에 맞는 학생 ID 번호를 가져옵니다
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//학생 ID 번호를 읽고 StuArray에서 학생 이름을 읽고 ClassArray에서 클래스 이름을 읽습니다.
echo "StudentName=".$StuArray[ $score['SID'] ]['STUNAME']."/t ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."/n";
}//각 학생의 ID를 가져오는 동안 종료 완료

개선된 방법의 시간 복잡도는 여전히 T(n)=O(1)입니다. 방법 1에 비해 방법 3은 특정 테이블의 레코드 증가로 인한 데이터베이스 쿼리 비용이 2배로 증가하는 것을 걱정할 필요가 없습니다. 방법 2와 비교하면 시간 복잡도는 줄어들지만 알고리즘 공간 복잡도에는 영향을 미치지 않습니다. 일석이조로 두 마리의 새를 잡는다고 할 수 있다.

이 최적화 방법이 간단하고 사용하기 쉽다고 해서 만능은 아닙니다. 그것을 사용할 때 "정도"의 문제를 고려해야 합니다. STUDENTS 테이블의 데이터 양이 크다고 가정하면 StuArray를 생성할 때 시스템 메모리 소비가 증가하며 이는 알고리즘의 공간 복잡도에 영향을 미칩니다. 또한, 데이터의 양이 충분히 커지면 알고리즘의 실행 시간에 영향을 미치는 주요 요인이 변경되어 원래 작업을 다시 선택해야 합니다. STUDENTS 테이블에 많은 수의 레코드가 있고 CLASSES 테이블에 소수의 안정적인 레코드가 있는 시나리오의 경우 중첩 쿼리와 배열의 조합을 사용하여 알고리즘을 최적화하는 것을 고려할 수 있습니다. 방법 4는 참조용으로 여기에 제공됩니다.

[방법 4] CLASSES 테이블에서 CLASSID와 CLASSNAME의 대응 관계를 얻어 ClassArray 1차원 배열에 저장합니다. SCORES 테이블에서 조건에 맞는 학생 ID 번호를 쿼리하고, 이를 STUDENTS 테이블 쿼리의 쿼리 조건으로 사용하여 학생의 STUNAME 및 CLASSID를 가져옵니다. 그런 다음 ClassArray에서 클래스 이름을 읽습니다. PHP 알고리즘은 다음과 같이 설명됩니다:

$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle ->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//ClassArray 배열을 생성합니다. 아래 첨자 Index는 CLASSID의 이름을 따서 명명되며 해당 값은 CLASSNAME
$ClassArray[$class['CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stusr = "STUDENTS에서 STUNAME,CLASSID를 선택하세요. ".
"(COURSE='M' 및 SCORE>=90인 SCORES에서 고유한 SID 선택)";
$studata = $db2handle->query($stusr);
//Get의 SID 데이터베이스에서 조건을 만족하는 조건 학생 이름과 학번
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//학생 이름을 읽고 ClassArray에서 학급 이름을 읽어옴
echo "StudentName=" .$stu ['STUNAME']."/t ";
echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."/n";
} //각 학생의 정보를 가져오는 동안 종료
 

방법 3과 4는 배열의 작은 트릭을 사용하여 알고리즘의 시간 복잡도를 교묘하게 줄입니다. 실제 응용에서는 알고리즘 논리가 훨씬 더 복잡하며, 알고리즘 최적화에는 여러 요소에 대한 포괄적인 고려가 필요합니다. 이 기사에서 설명하는 방법은 PHP 애플리케이션에만 적용되는 것이 아니라는 점을 언급해야 합니다. 프로그래밍 언어의 배열이 문자열을 첨자로 사용하는 것을 지원하는 경우 이 기사에서 제안한 방법 사용을 고려할 수 있습니다. 배열의 첨자를 영리하게 사용하여 알고리즘의 시간 복잡성을 줄입니다. 문자열을 배열 첨자로 지원하지 않는 프로그래밍 언어의 경우 해시 테이블을 사용하여 동일한 효과를 얻는 것을 고려할 수 있습니다.