这个算法做了多少次比较？ [英] How many comparisons does this algorithm make?

问题描述

我在伪代码中遇到了以下算法的考试问题。问题是：如果n等于10，会进行多少次比较？

I've come across an examination question with the algorithm below in pseudo code. The questions asks: "How many comparisons are made if n is equal 10?"

Algorithm sort
Declare A(1 to n)
n = length(A)
for i = 1 to n
    for j = 1 to n-1 inclusive do
        if A[i-1] > A[i] then
swap( A[i-1], A[i] )
        end if
    next j
next i

我尝试过：

What I have tried:

引用：

标记方案说它是100，但我认为这是错误的，并认为它是90.人们的意见是什么？

The marking scheme says it's 100 but I think this is wrong and think it's 90. What are people's opinions?

推荐答案

你是对的，如果 n 是，它会 90 比较10 。

（假设'包含'适用于两个循环）。

You are right, it does 90 comparisons if n is 10.
(assuming 'inclusive' applies to both the loops).

取决于，你可以得到72,80,81或者90.但可能不是100.

简单的方法来找出：试试吧！

Depends, you could get 72, 80, 81, or 90. But probably not 100.
Simple way to find out: try it!

int n = 10;
int count = 0;
for (int i = 1; i < n; i++)
    for (int j = 1; j < n - 1; j++)
        count++;
Console.WriteLine(count);            // 72
count = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j < n - 1; j++)
        count++;
Console.WriteLine(count);            // 80
count = 0;
for (int i = 1; i < n; i++)
    for (int j = 1; j <= n - 1; j++)
        count++;
Console.WriteLine(count);            // 81
count = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n - 1; j++)
        count++;
Console.WriteLine(count);            // 90

我自己？鉴于你的一个循环是特定的包容性而另一个不是我用81 ...

Myself? Given that one of your loops is specific about "inclusive" and the other isn't I'd go with 81 ...

这篇关于这个算法做了多少次比较？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！