• Дата реєстрації: 28.02.2023
  • Повідомлень: 2
    • Репутація: 0

Тема: Кількість ітерацій

як мені порахувати кількість ітерацій в даному алгоритмі?

for (int i = 0; i < size; i++) {
        int min_val = matrix[0][i];
        int max_val = matrix[0][i];
        int min_row = 0;
        int max_row = 0;
        for (int j = 0; j < size; j++) {
            if (matrix[j][i] < min_val) {
                min_val = matrix[j][i];
                min_row = j;
            }
            if (matrix[j][i] > max_val) {
                max_val = matrix[j][i];
                max_row = j;
            }
            
        }
        if (min_row < max_row) {
            for (int j = min_row + 1; j < max_row; j++) {

                matrix[j][i] = 3;
                
            }
        }
        else {
            for (int j = max_row + 1; j < min_row; j++) {
                matrix[j][i] = 3;
                
            }
        }
    }

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 321
    • Репутація: 13065

Re: Кількість ітерацій

Це ваш код? Що саме він робить?

koala вебсайт

  • Дата реєстрації: 28.02.2023
  • Повідомлень: 2
    • Репутація: 0

Re: Кількість ітерацій

цей код шукає мінімальний та максимальний елементи в стовпці матриці та всі елементи між ними змінює на 3

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 321
    • Репутація: 13065

Re: Кількість ітерацій

Якщо прийняти, що між мінімумом і максимумом у середньому 1/3 стовпця, то матимемо
цикл по i від 0 до size{
  цикл по j від 0 до size
  цикл по j від min до max (спрацює лише один)
}
разом - size*(size+size/3)=4/3*size2
У найгіршому разі (між екстремумами всюди весь стовпчик) буде size*(size+size-2)=2*size2-2*size, у найкращому (всі екстремуми поруч) - size*size.
Але зазвичай в алгоритмах оцінюється асимптотична складність, у цьому випадку - однозначно O(size2).

koala вебсайт

5 Відповідь від uzbdin1

  • uzbdin1
  • uzbdin1
  • Новий користувач
  • Поза форумом
  • Звідки: Ташкент
  • Дата реєстрації: 04.03.2023
  • Повідомлень: 3
    • Репутація: 2

Re: Кількість ітерацій

int count = 0; 
for (int i = 0; i < size; i++) { 
    int min_val = matrix[0][i]; 
    int max_val = matrix[0][i]; 
    int min_row = 0; 
    int max_row = 0; 
    for (int j = 0; j < size; j++) { 
        if (matrix[j][i] < min_val) { 
            min_val = matrix[j][i]; 
            min_row = j; 
        } 
        if (matrix[j][i] > max_val) { 
            max_val = matrix[j][i]; 
            max_row = j; 
        } 

        count++; 
         
    } 
    if (min_row < max_row) { 
        for (int j = min_row + 1; j < max_row; j++) { 

            matrix[j][i] = 3; 

            count++; 
             
        } 
    } 
    else { 
        for (int j = max_row + 1; j < min_row; j++) { 

            matrix[j][i] = 3;

            count++; 
             
        } 
    } 

    count++; 
}

cout << "The number of iterations is: " << count << endl;