Задачка (небольшая) =)

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by ENFIX, 4 Jul 2007.

  1. ENFIX

    ENFIX Elder - Старейшина

    Joined:
    6 Jun 2006
    Messages:
    175
    Likes Received:
    122
    Reputations:
    75
    Собственно текст:
    Следующий фрагмент программы записывает в переменную Max максимальный элемент в двухмерном массиве Dist размера NxN, заполненном целыми неотрицательными числами:
    Code:
    Max := 0;
    for i := 1 to N do
    for j := 1 to N do
    if Dist[i,j] > Max then Max := Dist[i,j]; 
    
    На очень медленном компьютере эта программа при N=1000 работала 5 секунд. Оцените время работы этой программы на том же компьютере при N=2000

    Варианты ответов:
    1) 10 сек.
    2) 20 сек.
    3) 30 сек.
    4) 40 сек.

    Хотелось бы увидеть ваш вариант ответов с аргумментированием ;)
     
    4 people like this.
  2. ak[id]

    ak[id] Elder - Старейшина

    Joined:
    22 Jun 2007
    Messages:
    143
    Likes Received:
    95
    Reputations:
    10
    4 вариант, т.к. массив двух мерный..
     
  3. sys32

    sys32 Banned

    Joined:
    4 Apr 2007
    Messages:
    86
    Likes Received:
    22
    Reputations:
    0
    сорак
     
  4. Y.Dmitriy

    Y.Dmitriy Banned

    Joined:
    14 Mar 2007
    Messages:
    208
    Likes Received:
    85
    Reputations:
    16
    насколько медленном?
     
  5. ENFIX

    ENFIX Elder - Старейшина

    Joined:
    6 Jun 2006
    Messages:
    175
    Likes Received:
    122
    Reputations:
    75
    Y.Dmitriy, просто медленном =) Неучитывается насколько (теоритически)
     
    1 person likes this.
  6. Y.Dmitriy

    Y.Dmitriy Banned

    Joined:
    14 Mar 2007
    Messages:
    208
    Likes Received:
    85
    Reputations:
    16
    тогда:
    4) 40 сек.
    потому как массив двумерный...
    ЗЫ Спасибки протормозил:)
    спать хочу пипец просто...
     
    #6 Y.Dmitriy, 4 Jul 2007
    Last edited: 4 Jul 2007
  7. ak[id]

    ak[id] Elder - Старейшина

    Joined:
    22 Jun 2007
    Messages:
    143
    Likes Received:
    95
    Reputations:
    10
    не, там же на два и массив и размер N заполненном целыми неотрицательными числами умножается=)
     
  8. Aristarh Dark

    Aristarh Dark Member

    Joined:
    14 Jun 2007
    Messages:
    7
    Likes Received:
    9
    Reputations:
    10
    При N=1000 имеем 1 000*1 000 = 1 000 000 элементов массива для проверки. При N = 2000 -> 2 000*2 000 = 4 000 000, т.е. в 4 раза больше. Зависимость квадратичная, следовательно при увеличении N в Y раз (в данном варианте задачи Y=2) затраты времени будут увеличены в Y^2 раз.
    Отсюда получаем 5*2^2=20 сек. Вариант ответа 2
     
    2 people like this.
Loading...