Треугольник Паскаля C# код космической сложности


можете ли вы дать мне ваше впечатление о моей реализации задачи треугольник Паскаля? Я особенно заинтересован в оценке сложности пространства спасибо всем!

public List<List<int>> generate(int A)
{
    List<List<int>> result = new List<List<int>>();

    int currenctRowLength = 1;
    List<int> previousRow = new List<int>();
    for (int i = 0; i < A; i++)
    {
        List<int> row = new List<int>();
        row.Add(1);
        currenctRowLength = i + 1;
        int j = 1;
        while (j < currenctRowLength - 1)
        {
            row.Add(previousRow[j] + previousRow[j - 1]);
            j++;
        }

        if (i > 0)
        {
            row.Add(1);
        }            

        previousRow=row;
        result.Add(row);
    }
    return result;
}


Комментарии
1 ответ

Как мне кажется, старик пытался сказать, если вы не знаете, что потребление памяти/распределение издержек являются серьезной проблемой, то этот код нормально с точки зрения памяти. Пространство-сложность такая же как вывод (в квадратичной A), Так что вы не можете сделать лучше, чем это.

Есть несколько небольших вещей, чтобы быть сказал:


  • а старик говорит: A совершенно бессмысленно, а надо бы lowerCamelCase имя в качестве параметра (например, dimension, size?); generate должно быть GeneratePascalTriangle или что-то значимое (общественно -> UpperCamelCase) (ссылка на MSDN)

  • currenctRowLength должно быть currentRowLengthи должны быть определены только внутри for петли (т. е. там, где он назначен); мне нравится, что это его собственное переменной.

  • вы используете while цикл по jкогда for может быть более читабельным (просто потому, что люди привыкли читать по-лупов), и не протекает j во внешнюю сферу.

  • List<List<int>> это довольно неприятный тип возвращается: намного лучше было IReadOnlyList<IReadOnlyList<T>> если возвращаемым значением должен быть неизменяемым (который присваиваем List<List<T>> или T[][]).

  • Я бы для начала previousRow для null, а не пустой список: не читал пока i == 2; назначение 'значимые' значение оборонительного и только может работать в непонятных глюков в остальной части кода.

Бездумное Исполнение Задумчивости

Если памяти/выделенных/ГК долбят является реальной проблемой, тогда вы можете улучшить положение, не используя масштабирование списков. Ты еще не дают нам никакого представления о том, что код на самом деле хотел сделать, так это немного трудно предложить альтернативу, но можно использовать массивы (которые, очевидно, не динамический), или вы можете сохранить подпись путем создания списков с заданной начальной емкостью с .ctor(int) перегрузки. Обратите внимание, что это даст бенефис, но изменить время-сложности (который также является квадратичной в A).

Код

Положить все это вместе (и использовать массивы вместо списков, потому что безмозглое представление-это весело, и я не думаю, что это вредит читабельности здесь много):

/// <summary>
/// Generates a pascal triangle with the given number of rows
/// </summary>
public static IReadOnlyList<IReadOnlyList<int>> GeneratePascalTriangle(int numberOfRows)
{
int[][] result = new int[numberOfRows][];

int[] previousRow = null;
for (int i = 0; i < numberOfRows; i++)
{
int currentRowLength = i + 1;

int[] row = new int[currentRowLength];
result[i] = row;

// start and end
row[0] = 1;
row[currentRowLength - 1] = 1;

// middle
for (int j = 1; j < currentRowLength - 1; j++)
{
row[j] = previousRow[j] + previousRow[j - 1];
}

previousRow = row;
}

return result;
}

2
ответ дан 28 января 2018 в 03:01 Источник Поделиться