VPF::[java]методы анализа алгоритмов - Форум программистов

ArniLand

Дата 7.11.2010, 23:40 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 227
Регистрация: 17.8.2008

Репутация: нет
Всего: нет

Написать программу на языке программирования Java2, осуществляющей анализ алгоритмов согласно варианту.
Выполните анализ эффективности алгоритмов последовательного и бинарного поиска данных в одномерном упорядоченном массиве размерностью М, М2, М3 (массив инициируется генератором случайных значений).

Как я понимаю, это нужно сделать с помощью встроенного метода System.nanotime(), но не знаю как это правильно сделать. Выкладываю, то что смог написать. Помогите пожалуйста организовать это в моей программе.

Код


public static void main(String[] args) {
        System.out.println("Введите М: ");
        Scanner in = new Scanner(System.in);
        int M = in.nextInt();
        
       
    }


    static int[] array1 (int M){
        int[] a = new int[M];
        Random r = new Random();
        for (int i = 0; i < M; i++)
            a[i] =  r.nextInt();
        return a;
    }

    public static int linearSearch(int array1[], int first, int upto, int key) {

    for (int i = first; i < upto; i++) {
        if (key == array1[i]) {
            return i;  
        }
    }
    return -1;
    }
     static int binSearch(int array1[], int el) {
        if (array1.length == 0) {
            return 0;
        }
        if (array1[array1.length - 1] < el) {
            return array1.length;
        }
        int i = 0;
        int j = array1.length;
        while (i + 1 < j) {
            int middle = i + (j - i) / 2;
            if (array1[middle] >= el) {
                j = middle;
            } else {
                i = middle;
            }
        }
        return array1[i] >= el ? i : j;
    }
}

Это сообщение отредактировал(а) ArniLand - 7.11.2010, 23:42

t_gran

Дата 12.11.2010, 08:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Какой-то странный у вас бинарный поиск. smile

В общем идея очень проста, запоминаете значение времени до и после выполнения алгоритма. Разница и есть время выполнения (в идеале smile

). Я правда убрал Random в следствие того, что не хотелось сортировать список. Запрос на ввод M я думаю сами сделаете.

Код


class TAnalysis
{
   protected int arr[];

   public TAnalysis(int theLength)
   {
      arr = new int[theLength];
      for (int i: arr)
         arr[i] = i+1;
   }

   public void Show()
   {
      for (int i: arr)
         System.out.print(arr[i] + " ");
   }

   public int SearchLinear(int theKey)
   {
      for (int i: arr)
         if (arr[i] == theKey)
            return i;
      return -1;
   }

   public int TimeSearchLinear(int theKey)
   {
      long begin = System.nanoTime();
      SearchLinear(theKey);
      return (int)(System.nanoTime() - begin);
   }

   public int SearchBinary(int theKey)
   {
      int left = 0;
      int right = arr.length - 1;

      while (left <= right)
      {
         int middle = (right + left) / 2;
         if (arr[middle] == theKey)
            return middle;
         else if (arr[middle] > theKey)
            right = middle - 1;
         else
            left = middle + 1;
      }

      return -1;
   }

   public int TimeSearchBinary(int theKey)
   {
      long begin = System.nanoTime();
      SearchBinary(theKey);
      return (int)(System.nanoTime() - begin);
   }
}


public class TMain
{
   public static void main(String args[])
   {
      TAnalysis analysis = new TAnalysis(1000);

      //System.out.println(analysis.SearchLinear(234));
      //System.out.println(analysis.SearchBinary(234));

      System.out.println(analysis.TimeSearchLinear(345));
      System.out.println(analysis.TimeSearchBinary(345));
   }
}

Это сообщение отредактировал(а) t_gran - 12.11.2010, 09:13

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »