1
function solution(A) {
var len = A.length;
cnt = 0;
for(i = 0; i < len - 1; i++){
for (a = i + 1; a < len; a++){
if (A[i] == A[a]){cnt++;}
else{continue;}
}
if(cnt > 1000000000){return 1000000000;}
}
return cnt;
}
Так что это код для подсчета идентичных пар массива, я знаю, что 2 для петель дает временную сложность O (п). Это всегда так? Даже если следующая итерация проходит через только оставшуюся часть массива?Сложность вложенных циклов для начиная с последней итерации
посмотреть здесь: [ссылка] (HTTP://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop) duplicate – guymaor86
Да, дело в том, что я не перебираю список с самого начала, как в предложенной вами ссылке, я повторяю n-1 раз во второй раз и т. д., все-таки означает, что я получаю такую же сложность? –
Ссылка, которую я разместил, почти то же самое, что и зеркало. Просто внимательно посмотрите на нее, и вы ее получите. Но в любом случае такая же сложность. 1 + 2 + 3 + .. + n = (n^2 + n)/2, который равен O (n^2) – guymaor86