동일한 for 루프에서 비교 횟수가 시간 복잡도에 영향을 줍니까?

Question

예제 연습에서는 배열의 모든 요소가 서로 동일한 지 확인했습니다. 이 질문은이 작업을 수행하는 가장 효율적인 방법에 관한 것이 아닙니다. 오히려이 두 가지 솔루션에 관한 것입니다.

for(var i=0; i < set.length-1; i++) 
    { 
    if (set[i] != set[i+1]) // could have compared all elements to the firstelement instead of switching 
    { 
    isTrue=false; 
    } 

    } 

위의 알고리즘은 각 인덱스를 인덱스와 나중에 비교합니다.

var firstIndex=set[0]; 
for(var i=0; i < set.length-1; i++) 
{ 
    if(set[i] != firstIndex) 
    { 
     isTrue=false; 
    } 
} 

이 알고리즘은 현재 색인과 첫 번째 색인을 비교합니다. 이러한 알고리즘은 적어도 O (N)이지만. 비교의 차이가 시간/공간 복잡성에 영향을 줍니까?

Answer 1

음

시간 복잡성을 분명히 일을 할 수 있습니다. 공간 복잡도는 O(1)입니다.

배열 색인 액세스 또는 기타 같은 것은 Big-O 시간 복잡성에 영향을주지 않습니다.

이러한 알고리즘은 적어도 O (N)이지만.

이들은 적어도 O(n)입니다.

당신은 조건이`내가

if(set[i] != firstIndex) 
{ 
    isTrue=false; 
    break; 
} 

Answer 2

공간 복잡성 : 여분의 변수/데이터 구조를 사용하지 않아도 변경되지 않습니다. 두 번째 코드 단편에있는 firstIndex은 일정한 공간을 차지하므로 고려하지 않습니다.

시간 복잡도 : 거의 변화 없음. 두 조각 모두에서 단일 비교를 수행하지만 배열 액세스가 직접 변수 액세스와 비교할 때 속도가 느리기 때문에 첫 번째 코드 조각은 조금 느려집니다. 둘 다 O(n) 될 것이기